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

(x)_{(n)} = \sum_{k=0}^n s(n,k) x^k.

where (x)(n) is the falling factorial

(x)_{(n)}=x(x-1)(x-2)\cdots(x-n+1).

[edit] Unsigned Stirling numbers of the first kind

The unsigned Stirling numbers of the first kind

\left[{n \atop k}\right] = \left|s(n,k)\right| = (-1)^{n-k} s(n,k)\,

count the number of permutations of n elements with k disjoint cycles. Sometimes s(n,k) is defined as the unsigned Stirling numbers.

[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

\left[{n+1\atop k}\right] = n \left[{n\atop k}\right] + \left[{n\atop k-1}\right]

for k > 0, with the initial conditions

\left[{n\atop 0}\right]=\delta_{n0} \quad \mbox{and} \quad \left[{0\atop 1}\right] = 0.

Where δn0 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

\left[{0 \atop 0}\right] = 1\quad\mbox{we have}\quad\left[{n\atop 0}\right] = 0\quad \mbox{if} \quad n > 0

and

\left[{0\atop k}\right] = 0\quad\mbox{if}\quad k > 0,\quad\mbox{or more generally,}\quad \left[{n\atop k}\right] = 0\quad\mbox{if}\quad k>n.

Also

\left[{n \atop 1}\right] = (-1)^{n-1} (n-1)!

and

\left[{n\atop n}\right] = 1, \quad \left[{n\atop n-1}\right] = {n \choose 2},

and

\left[{n\atop n-2}\right] = \frac{1}{4} (3n-1) {n \choose 3}\quad\mbox{ and }\quad\left[{n\atop n-3}\right] = {n \choose 2} {n \choose 4}.

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] 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 − 5 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:
{n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6}
  • 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:
{n \choose 5} {5 \choose 3} \times 2
  • choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
{n \choose 4} \times 6.

Sum the three contributions to obtain

{n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6} + {n \choose 5} {5 \choose 3} \times 2 + {n \choose 4} \times 6 = {n \choose 2} {n \choose 4}.

[edit] Other relations

These include

\left[{n\atop 2}\right] = (n-1)!\; H_{n-1},

where Hn is a harmonic number, and

\left[{n\atop 3}\right] = \frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]

where Hn(m) 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:

H(z,u)= (1+z)^u = \sum_{n=0}^\infty {u \choose n} z^n = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{k=0}^n \left[{n\atop k}\right] u^k = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} \left[{n\atop k}\right] = e^{u\log(1+z)}.

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

\sum_{k=0}^n \left[{n\atop k}\right] = n!

or in a more general relationship,

\sum_{k=0}^a \left[{n\atop k}\right] = n! - \sum_{k=0}^n \left[{n\atop k+a+1}\right].

The identity

\sum_{p=k}^{n} {\left[{n\atop p}\right]\binom{p}{k}} = \left[{n+1\atop k+1}\right]

is proved on the page about Stirling numbers and exponential generating functions.

[edit] Infinite sums

Some infinite sums include

\sum_{n=k}^\infty (-1)^{n-k} \left[{n\atop k}\right] \frac{z^n}{n!} = \frac{\left(\log (1+z)\right)^k}{k!}

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

H^{(m)}_n=\sum_{k=1}^n \frac{1}{k^m}

as follows:

s(n,k)=(-1)^{k-n} \frac{\Gamma(n)}{\Gamma(k)}w(n,k-1)

where w(n, 0) = 1 and

w(n,k)=\sum_{m=0}^{k-1}\frac{\Gamma(1-k+m)}{\Gamma(1-k)}H_{n-1}^{(m+1)} w(n,k-1-m).

In the above, Γ(x) is the Gamma function.

[edit] Enumerative interpretation

s(4,2)=11
s(4,2)=11

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

(\bullet\bullet)(\bullet\bullet) — 2 orbits of size 2 each

and 8 permutations of the form

(\bullet\bullet\bullet) — 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:

| s(n+1,k)| = | s(n,k-1)| + n| s(n,k)|,\qquad 1\leq k < n.

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 objects with k cycles, and label the objects a1, ..., an, so that the permutation is represented by

\displaystyle\underbrace{(a_1 \ldots a_{j_1})(a_{j_1+1} \ldots a_{j_2})\ldots(a_{j_{k-1}+1} \ldots a_n)}_{ k\ \mathrm{cycles}}.

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 n s(n, k) term of the recurrence relation. Q.E.D.

[edit] References

This article incorporates material from Stirling numbers of the first kind on PlanetMath, which is licensed under the GFDL.