In combinatorial mathematics, the Stirling transform of a sequence { a<sub>n</sub> : n = 1, 2, 3, ... } of numbers is the sequence { b<sub>n</sub> : n = 1, 2, 3, ... } given by

:<math>b_n=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix} \right\} a_k</math>,

where <math>\left\{\begin{matrix} n \\ k \end{matrix} \right\}</math> is the Stirling number of the second kind, which is the number of partitions of a set of size <math>n</math> into <math>k</math> parts. This is a linear sequence transformation.

The inverse transform is

:<math>a_n=\sum_{k=1}^n (-1)^{n-k} \left[{n \atop k}\right] b_k</math>,

where <math display="inline">(-1)^{n-k} \left[{n\atop k}\right]</math> is a signed Stirling number of the first kind, where the unsigned <math>\left[{n\atop k}\right]</math> can be defined as the number of permutations on <math>n</math> elements with <math>k</math> cycles.

Berstein and Sloane (cited below) state "If a<sub>n</sub> 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<sub>n</sub> is the number of objects with points labeled 1, 2, ..., n (with repetitions allowed)."

If

:<math>f(x) = \sum_{n=1}^\infty {a_n \over n!} x^n</math>

is a formal power series, and

:<math>g(x) = \sum_{n=1}^\infty {b_n \over n!} x^n</math>

with a<sub>n</sub> and b<sub>n</sub> as above, then

:<math>g(x) = f(e^x-1)</math>.

Likewise, the inverse transform leads to the generating function identity

:<math>f(x) = g(\log(1+x))</math>.

See also

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

References

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