![]() | ||
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one).
Contents
- Definitions
- Unsigned Stirling numbers of the first kind
- Stirling numbers of the first kind
- Recurrence relation
- Algebraic proof
- Combinatorial proof
- Table of values for small n and k
- Simple identities
- Combinatorial proofs
- Other relations
- Generating function
- Finite sums
- Explicit formula
- References
(The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind. Identities linking the two kinds appear in the article on Stirling numbers in general.)
Definitions
The original definition of Stirling numbers of the first kind was algebraic. These numbers, usually written s(n, k), are signed integers whose sign, positive or negative, depends on the parity of n − k. Afterwards, the absolute values of these numbers, |s(n, k)|, which are known as unsigned Stirling numbers of the first kind, were found to count permutations, so in combinatorics the (signed) Stirling numbers of the first kind, s(n, k), are often defined as counting numbers multiplied by a sign factor. That is the approach taken on this page.
Most identities on this page are stated for unsigned Stirling numbers. Note that the notations on this page are not universal.
Unsigned Stirling numbers of the first kind
The unsigned Stirling numbers of the first kind are denoted in various ways by different authors. Common notations are
As a second example, the image at right shows that
and 8 permutations of the form
The unsigned Stirling numbers also arise as coefficients of the rising factorial, i.e.,
Thus, for example,
Stirling numbers of the first kind
Stirling numbers of the first kind (sometimes with the qualifying adjective signed) are given by
They are the coefficients in the expansion
where
Note that
Recurrence relation
The unsigned Stirling numbers of the first kind can be calculated by the recurrence relation
for
for n > 0.
It follows immediately that the (signed) Stirling numbers of the first kind satisfy the recurrence
Algebraic proof
We prove the recurrence relation using the definition of Stirling numbers in terms of rising factorials. Distributing the last term of the product, we have
The coefficient of xk on the left-hand side of this equation is
Combinatorial proof
We prove the recurrence relation using the definition of Stirling numbers in terms of permutations with a given number of cycles (or equivalently, orbits).
Consider forming a permutation of n + 1 objects from a permutation of n objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the
To form a new permutation of n + 1 objects and k cycles one must insert the new object into this array. There are n ways to perform this insertion, inserting the new object immediately following any of the n already present. This explains the
Table of values for small n and k
Below is a triangular array of unsigned values for the Stirling numbers of the first kind, similar in form to Pascal's triangle. These values are easy to generate using the recurrence relation in the previous section.
Simple identities
Note that although
and
Also
and
Similar relationships involving the Stirling numbers hold for the Bernoulli polynomials. Many relations for the Stirling numbers shadow similar relations on the binomial coefficients. The study of these 'shadow relationships' is termed umbral calculus and culminates in the theory of Sheffer sequences.
Combinatorial proofs
These identities may be derived by enumerating permutations directly. For example, a permutation of n elements with n − 3 cycles must have one of the following forms:
The three types may be enumerated as follows:
Sum the three contributions to obtain
Other relations
Other relations involving Stirling numbers of the first kind include
where Hn is a harmonic number, and
where Hn(m) is a generalized harmonic number. For a generalization of this relation, see below.
For all positive integer m and n we have that
where
Generating function
A variety of identities may be derived by manipulating the generating function:
Using the equality
it follows that
(This identity is valid for formal power series, and the sum converges in the complex plane for |z| < 1.) Other identities arise by exchanging the order of summation, taking derivatives, making substitutions for z or u, etc. For example, we may derive:
and
where
Finite sums
Since permutations are partitioned by number of cycles, one has
The identity
can be proved by the techniques on the page Stirling numbers and exponential generating functions.
Explicit formula
The Stirling number s(n,n-p) can be found from the formula
where