Stirling transform
Encyclopedia
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, 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
where s(n,k) (with a lower-case s) is a Stirling number of the first kind.
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
(note that the lower bound of summation is 1, not 0), and
with an and bn as above, then
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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 numberStirling number
In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second...
of the second kind, also denoted S(n,k) (with a capital S), which is the number of partitions
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of a set of size n into k parts.
The inverse transform is
where s(n,k) (with a lower-case s) is a Stirling number of the first kind.
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
Formal power series
In mathematics, formal power series are a generalization of polynomials as formal objects, where the number of terms is allowed to be infinite; this implies giving up the possibility to substitute arbitrary values for indeterminates...
(note that the lower bound of summation is 1, not 0), and
with an and bn as above, then