Stirling numbers of the first kind

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).

(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

s(4,2)=11

The unsigned Stirling numbers of the first kind are denoted in various ways by different authors. Common notations are $c(n,k),$ $|s(n,k)|$ and $\left[{n\atop k}\right]$. (The last is also common notation for the Gaussian coefficients.) They count the number of permutations of n elements with k disjoint cycles. For example, of the $3! = 6$ permutations of three elements, there is one permutation with three cycles (the identity permutation, given in one-line notation by $123$ or in cycle notation by $(1)(2)(3)$), three permutations with two cycles ($132 = (1)(23)$, $213 = (3)(12)$, and $321 = (2)(13)$) and two permutations with one cycle ($312 = (132)$ and $231 = (123)$). Thus, $\left[{3\atop 3}\right] = 1$, $\left[{3\atop 2}\right] = 3$ and $\left[{3\atop 1}\right] = 2$.

As a second example, the image at right shows that $\left[{4\atop 2}\right] = 11$: the symmetric group on 4 objects has 3 permutations of the form

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

and 8 permutations of the form

$(\bullet\bullet\bullet)(\bullet)$—1 orbit of size 3 and 1 orbit of size 1.

The unsigned Stirling numbers also arise as coefficients of the rising factorial, i.e.,

$(x)^{(n)} = x(x+1)\cdots(x+n-1)=\sum_{k=0}^n \left[{n\atop k}\right] x^k$.

Thus, for example, $(x)^{(3)} = x(x + 1)(x + 2) = 1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x$, which matches the computations in the preceding paragraph.

Stirling numbers of the first kind

Stirling numbers of the first kind (sometimes with the qualifying adjective signed) are given by

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

They 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).$

Note that

$\left[{n \atop k}\right] = \left|s(n,k)\right| .$

Recurrence relation

The unsigned Stirling numbers of the first kind can be calculated by 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[{0\atop 0}\right] = 1 \quad\mbox{and}\quad \left[{n\atop 0}\right]=\left[{0\atop n}\right]=0$

for n > 0.

It follows immediately that the (signed) Stirling numbers of the first kind satisfy the recurrence

$s(n + 1, k) = -n s(n, k) + s(n, k - 1)$.

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

$(x)^{(n+1)} = x(x+1)\cdots (x+n-1)(x+n)=n(x)^{(n)}+x(x)^{(n)}.$

The coefficient of x^k on the left-hand side of this equation is $\left[{n+1\atop k}\right]$. The coefficient of x^k in n(x)⁽ⁿ⁾ is $n \cdot \left[{n\atop k}\right]$, while the coefficient of x^k in x (x)⁽ⁿ⁾ is $\left[{n\atop k - 1}\right]$. Since the two sides are equal as polynomials, the coefficients of x^k on both sides must be equal, and the result follows.

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 $\left[{n\atop k-1}\right]$ 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 a₁, ..., a_n, 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 n ways to perform this insertion, inserting the new object immediately following any of the n already present. This explains the $n \left[{n\atop k}\right]$ term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows.

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.

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

Identities involving Stirling numbers of the first kind

Simple identities

Note that although

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

and

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

Also

$\left[{n \atop 1}\right] = (n-1)!, \quad \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.

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:

• n − 6 fixed points and three two-cycles
• n − 5 fixed points, a three-cycle and a two-cycle, or
• n − 4 fixed points and a four-cycle.

The three types may be enumerated 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}.$

Other relations

Other relations involving Stirling numbers of the first kind include

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

where H_n 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]$

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

where H_n^(m) is a generalized harmonic number. For a generalization of this relation, see below.

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 s(n,k) u^k = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} s(n,k).$

Using the equality

$(1+z)^u = e^{u\log(1+z)} = \sum_{k = 0}^\infty (\log(1 + z))^k \frac{u^k}{k!},$

it follows that

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

(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:

$(1-z)^{-u} = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} \left[{n\atop k}\right] = e^{u\log(1/(1-z))}$

and

$\sum_{n=i}^\infty \frac{\left[{n\atop i}\right]}{n (n!)} = \zeta(i+1)$

where $\zeta(k)$ is the Riemann zeta function.

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]$

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^[1]

$\begin{align} s(n,n-p) &= \frac{1}{(n-p-1)!} \sum_{0 \leq k_1, \ldots , k_p : \sum_2^p mk_m = p} (-1)^K \frac{(n+K-1)!}{k_2! \cdots k_p! ~ 1!^{k_1} 2!^{k_2} 3!^{k_3} \cdots p!^{k_p}} , \end{align}$

where $K =k_2 + \cdots + k_p.$ The sum is a sum over all partitions of p.

See also

• Stirling polynomials

References

1. J. Malenfant, "Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers"

• The Art of Computer Programming
• Concrete Mathematics
• M. Abramowitz, I. Stegun, ed. (1972). "§24.1.3. Stirling Numbers of the First Kind". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (9th ed.). New York: Dover. p. 824.
• Stirling numbers of the first kind, s(n,k) at PlanetMath.org. .
• "Sloane's A008275 : Triangle read by rows of Stirling numbers of first kind", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

This article incorporates material from Stirling numbers of the first kind on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.