Stirling transform

In combinatorial mathematics, the Stirling transform of a sequence { a_n : n = 1, 2, 3, ... } of numbers is the sequence { b_n : n = 1, 2, 3, ... } given by

b_{n}=\sum _{{k=1}}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}a_{k},

where $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ is the Stirling number of the second kind, also denoted S(n,k) (with a capital S), which is the number of partitions of a set of size n into k parts.

The inverse transform is

a_{n}=\sum _{{k=1}}^{n}s(n,k)b_{k},

where s(n,k) (with a lower-case s) is a Stirling number of the first kind.

Berstein and Sloane (cited below) state "If a_n is the number of objects in some class with points labeled 1, 2, ..., n (with all labels distinct, i.e. ordinary labeled structures), then b_n is the number of objects with points labeled 1, 2, ..., n (with repetitions allowed)."

f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}

is a formal power series (note that the lower bound of summation is 1, not 0), and

g(x)=\sum _{{n=1}}^{\infty }{b_{n} \over n!}x^{n}

with a_n and b_n as above, then

g(x)=f(e^{x}-1).\,

References

Bernstein, M.; Sloane, N. J. A. (1995). "Some canonical sequences of integers". Linear Algebra and its Applications. 226/228: 57–72. doi:10.1016/0024-3795(94)00245-9. .

This article is issued from Wikipedia - version of the 3/28/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Stirling transform

See also

References