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>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, 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>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>f(x)=\sum_{n=1}^\infty {a_n \over n!} x^n<math>

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

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

with a_n and b_n as above, then

<math>g(x)=f(e^x-1).\,<math>

Reference

• M. Bernstein and N. J. A. Sloane, "Some canonical sequences of integers", Linear Algebra and Applications, 226/228 (1995), 57–72.