Stirling transform

Summary

In combinatorial mathematics, the Stirling transform of a sequence { an : n = 1, 2, 3, ... } of numbers is the sequence { bn : n = 1, 2, 3, ... } given by

,

where is the Stirling number of the second kind, which is the number of partitions of a set of size into parts. This is a linear sequence transformation.

The inverse transform is

,

where is a signed Stirling number of the first kind, where the unsigned can be defined as the number of permutations on elements with cycles.

Berstein and Sloane (cited below) state "If an is the number of objects in some class with points labeled 1, 2, ..., n (with all labels distinct, i.e. ordinary labeled structures), then bn is the number of objects with points labeled 1, 2, ..., n (with repetitions allowed)."

If

is a formal power series, and

with an and bn as above, then

.

Likewise, the inverse transform leads to the generating function identity

.

See also

edit

References

edit
  • 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.