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{array}{c}n\\ k\end{array}\right\}{a}_k$,

where $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ is the Stirling number of the second kind, which is the number of partitions of a set of size $n$ into $k$ parts. This is a linear sequence transformation.

The inverse transform is

$a_n=\sum _{k=1}^n(-1{)}^{n-k}\left[\genfrac{}{}{0ex}{}{n}{k}\right]b_k$,

where $(-1{)}^{n-k}\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ is a signed Stirling number of the first kind, where the unsigned $\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ can be defined as the number of permutations on $n$ elements with $k$ cycles.

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)."

If

$f(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n$

is a formal power series, and

$g(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{b_n}{n!}{x}^n$

with a_n and b_n as above, then

$g(x)=f(e^x-1)$.

Likewise, the inverse transform leads to the generating function identity

$f(x)=g(\log (1+x))$.

See also

• Binomial transform
• Generating function transformation
• List of factorial and binomial topics

References

• Template:Cite journal.
• Khristo N. Boyadzhiev, Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.