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=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix} \right\} a_k , where \left\{\begin{matrix} n \\ k \end{matrix} \right\} 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=\sum_{k=1}^n (-1)^{n-k} \left[{n \atop k}\right] b_k , where (-1)^{n-k} \left[{n\atop k}\right] is a signed Stirling number of the first kind, where the unsigned \left[{n\atop k}\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) = \sum_{n=1}^\infty {a_n \over n!} x^n is a formal power series, 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) . Likewise, the inverse transform leads to the generating function identity : f(x) = g(\log(1+x)) .

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=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix} \right\} a_k , where \left\{\begin{matrix} n \\ k \end{matrix} \right\} 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=\sum_{k=1}^n (-1)^{n-k} \left[{n \atop k}\right] b_k , where (-1)^{n-k} \left[{n\atop k}\right] is a signed Stirling number of the first kind, where the unsigned \left[{n\atop k}\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) = \sum_{n=1}^\infty {a_n \over n!} x^n is a formal power series, 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) . Likewise, the inverse transform leads to the generating function identity f(x) = g(\log(1+x)) .

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371072699 under CC BY-SA 4.0; modifications have been made.