Stirling transform
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 b n = ∑ k = 1 n { n k } a k {\displaystyle b_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}a_{k}} , where { n k } {\displaystyle \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 {\displaystyle n} into k {\displaystyle k} parts. This is a linear sequence transformation. The inverse transform is a n = ∑ k = 1 n ( − 1 ) n − k [ n k ] b k {\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{n-k}\left[{n \atop k}\right]b_{k}} , where ( − 1 ) n − k [ n k ] {\textstyle (-1)^{n-k}\left[{n \atop k}\right]} is a signed Stirling number of the first kind, where the unsigned [ n k ] {\displaystyle \left[{n \atop k}\right]} can be defined as the number of permutations on n {\displaystyle n} elements with k {\displaystyle k} 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 f ( x ) = ∑ n = 1 ∞ a n n ! x n {\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}} is a formal power series, and g ( x ) = ∑ n = 1 ∞ b n n ! x n {\displaystyle g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n}} with an and bn as above, then g ( x ) = f ( e x − 1 ) {\displaystyle g(x)=f(e^{x}-1)} . Likewise, the inverse transform leads to the generating function identity f ( x ) = g ( log ( 1 + x ) ) {\displaystyle f(x)=g(\log(1+x))} .
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
- ,
![{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{n-k}\left[{n \atop k}\right]b_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b99352463fb9a4bacf6a28a7f79e5c684b4f076)
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.
![{\textstyle (-1)^{n-k}\left[{n \atop k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/010cbbee14fc66698377c583ea15f4071cae684a)
![{\displaystyle \left[{n \atop k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53e244be41a40ffd185e9edea632ba557f6ad945)
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.