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

[math]\displaystyle{ b_n=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix} \right\} a_k, }[/math]

where [math]\displaystyle{ \left\{\begin{matrix} n \\ k \end{matrix} \right\} }[/math] 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

[math]\displaystyle{ a_n=\sum_{k=1}^n s(n,k) b_k, }[/math]

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

If

[math]\displaystyle{ f(x) = \sum_{n=1}^\infty {a_n \over n!} x^n }[/math]

is a formal power series, and

[math]\displaystyle{ g(x) = \sum_{n=1}^\infty {b_n \over n!} x^n }[/math]

with a_n and b_n as above, then

[math]\displaystyle{ g(x) = f(e^x-1).\, }[/math]

Likewise, the inverse transform leads to the generating function identity

[math]\displaystyle{ f(x) = g(\log(1+x)). }[/math]

See also

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

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. .
• Khristo N. Boyadzhiev, Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.