In
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Stirling transform of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of numbers is the sequence 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
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
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 ''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
:
is a
formal power series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
, and
:
with ''a''
''n'' and ''b''
''n'' as above, then
:
Likewise, the inverse transform leads to the
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
identity
:
See also
*
Binomial transform In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to th ...
*
Generating function transformation
In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formula ...
*
List of factorial and binomial topics {{Short description, none
This is a list of factorial and binomial topics in mathematics. See also binomial (disambiguation).
* Abel's binomial theorem
* Alternating factorial
*Antichain
*Beta function
*Bhargava factorial
*Binomial coefficient
**P ...
References
* {{cite journal, first1=M. , last1=Bernstein , first2=N. J. A. , last2=Sloane
, title=Some canonical sequences of integers , journal=Linear Algebra and its Applications
, volume=226/228 , year=1995 , pages=57–72 , doi=10.1016/0024-3795(94)00245-9, arxiv=math/0205301 .
* Khristo N. Boyadzhiev, ''Notes on the Binomial Transform, Theory and Table, with Appendix on the Stirling Transform'' (2018), World Scientific.
Factorial and binomial topics
Transforms