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=\backslash sum\_\{k=1\}^n\; \backslash left\backslash \{\backslash begin\{matrix\}\; n\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right\backslash \}\; a\_k$,

where $\backslash left\backslash \{\backslash begin\{matrix\}\; n\; \backslash \backslash \; k\; \backslash end\{matrix\}\; \backslash right\backslash \}$ 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=\backslash sum\_\{k=1\}^n\; (-1)^\{n-k\}\; \backslash left[\{n\; \backslash atop\; k\}\backslash right]\; b\_k$,

where $(-1)^\{n-k\}\; \backslash left[\{n\backslash atop\; k\}\backslash right]$ is a signed Stirling number of the first kind, where the unsigned $\backslash left[\{n\backslash atop\; k\}\backslash 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)\; =\; \backslash sum\_\{n=1\}^\backslash infty\; \{a\_n\; \backslash over\; n!\}\; x^n$

is a formal power series, and

:$g(x)\; =\; \backslash sum\_\{n=1\}^\backslash infty\; \{b\_n\; \backslash over\; 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(\backslash log(1+x))$.