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

:

where 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

:$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

:$f(x)=sum\_\{n=1\}^infty\; \{a\_n\; over\; n!\}\; x^n$

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

:$g(x)=sum\_\{n=1\}^infty\; \{b\_n\; over\; n!\}\; x^n$

with "a"_"n" and "b"_"n" as above, then

:$g(x)=f(e^x-1).,$

ee also

* Binomial transform
* List of factorial and binomial topics

References

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