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

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

where ${\displaystyle \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

${\displaystyle 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)."

If

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

is a formal power series, and

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

with a_n and b_n as above, then

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

Likewise, the inverse transform leads to the generating function identity

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

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. arXiv:math/0205301. doi:10.1016/0024-3795(94)00245-9. S2CID 14672360..
• Khristo N. Boyadzhiev, Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform (2018), World Scientific.

This page was last edited on 11 February 2023, at 02:14