Stirling numbers of the first kind
From Wikipedia, the free encyclopedia
In mathematics, Stirling numbers of the first kind, together with the Stirling numbers of the second kind, are one of the two types of Stirling numbers. They commonly occur in the study of combinatorics, where they count the number of permutations. The Stirling numbers of the first and second kind can be understood to be inverses of one-another, when taken as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind; further identities linking the two kinds, and general information, is given in the article on Stirling numbers.
Contents |
[edit] Definition
[edit] Stirling numbers of the first kind
Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion
where (x)n is the falling factorial
[edit] Unsigned Stirling numbers of the first kind
The unsigned Stirling numbers of the first kind
count the number of permutations of n elements with k disjoint cycles. Sometimes s(n,k) is defined as the unsigned Stirling numbers.
[edit] Alternate notation
Stirling numbers of the first kind are sometimes written with the alternate notation
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.
[edit] Table of values
Below is a table of values for the Stirling numbers of the first kind, similar in form to Pascal's triangle:
n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 1 | |||||||||
1 | 0 | 1 | ||||||||
2 | 0 | −1 | 1 | |||||||
3 | 0 | 2 | −3 | 1 | ||||||
4 | 0 | −6 | 11 | −6 | 1 | |||||
5 | 0 | 24 | −50 | 35 | −10 | 1 | ||||
6 | 0 | −120 | 274 | −225 | 85 | −15 | 1 | |||
7 | 0 | 720 | −1764 | 1624 | −735 | 175 | −21 | 1 | ||
8 | 0 | −5040 | 13068 | −13132 | 6769 | −1960 | 322 | −28 | 1 | |
9 | 0 | 40320 | −109584 | 118124 | −67284 | 22449 | −4536 | 546 | −36 | 1 |
[edit] Recurrence relation
The Stirling numbers of the first kind obey the recurrence relation
for k > 0, with the initial conditions
Where δn is the Kronecker delta.
The above follows from the recurrence relation on the falling factorials:
- (x)n + 1 = x(x)n − n(x)n.
[edit] Simple identities
Note that although
and
Also
and
and
[edit] Combinatorial proofs
These identities may be derived by enumerating permutations directly. For example, how many permutations on [n] are there that consist of n − 3 cycles? There are three possibilities:
- n − 6 fixed points and three two-cycles
- n − 5 fixed points, a three-cycle and a two-cycle, and
- n − 4 fixed points and a four-cycle.
We enumerate the three types, as follows:
- choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important:
- choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles:
- choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
Sum the three contributions to obtain
[edit] Other relations
These include
where Hn is a harmonic number, and
where is a generalized harmonic number. A generalization of this relation to harmonic numbers is given in a later section.
[edit] Generating function
A variety of identities may be derived by manipulating the generating function:
In particular, the order of summation may be exchanged, and derivatives taken, and then z or u may be fixed.
[edit] Finite sums
A simple sum is
or in a more general relationship,
The identity
is proved on the page about Stirling numbers and exponential generating functions.
[edit] Infinite sums
Some infinite sums include
where | z | < 1 (the singularity nearest to z = 0 of log(1 + z) is at z = − 1.)
[edit] Relation to harmonic numbers
Stirling numbers of the first kind can be expressed in terms of the harmonic numbers
as follows:
where w(n,0) = 1 and
In the above, Γ(x) is the Gamma function.
[edit] Enumerative interpretation
The absolute value of the Stirling number of the first kind, s(n,k), counts the number of permutations of n objects with exactly k orbits (equivalently, with exactly k cycles). For example, s(4,2) = 11, corresponds to the fact that the symmetric group on 4 objects has 3 permutations of the form
- — 2 orbits of size 2 each
and 8 permutations of the form
- — 1 orbit of size 3, and 1 orbit of size 1
(see the entry on cycle notation for the meaning of the above expressions.)
Let us prove this. First, we can remark that the unsigned Stirling numbers of the first are characterized by the following recurrence relation:
To see why the above recurrence relation matches the count of permutations with k cycles, 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 accounts for the s(n,k − 1) term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of n object with k cycles, and label the objects , so that the permutation is represented by
To form a new permutation of n + 1 objects and k cycles one must insert the new object into this array. There are, evidently n ways to perform this insertion. This explains the term of the recurrence relation. Q.E.D.
[edit] References
- M. Abramowitz, I. Stegun (Eds.). Stirling Numbers of the First Kind., §24.1.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 824, 1972.
- Stirling numbers of the first kind, s(n,k) on PlanetMath.
This article incorporates material from Stirling numbers of the first kind on PlanetMath, which is licensed under the GFDL.