Stirling number

In mathematics, Stirling numbers arise in a variety of combinatorics problems. They are named after James Stirling, who introduced them in the 18th century. Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind.

Notation

Several different notations for the Stirling numbers are in use. Stirling numbers of the first kind are written with a small s, and those of the second kind with a large S:

s(n,k)=\left[{\begin{matrix}n\\k\end{matrix}}\right].

S(n,k)=S_{n}^{(k)}=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}.

The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation.

Stirling numbers of the first kind

In combinatorial mathematics, unsigned Stirling numbers of the first kind

s(n,k)\,

(with a lower-case "s") count the number of permutations of n elements with k disjoint cycles.

Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion

x^{n}=\sum _{k=1}^{n}s(n,k)(x)^{k}

where (x)ⁿ is the rising factorial

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

Stirling numbers of the first kind are sometimes written with the alternate notation

s(n,k)=\left[{\begin{matrix}n\\k\end{matrix}}\right].

The definition can be inverted to express the falling factorial as a power series:

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

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.

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

Recurrence relation

The Stirling numbers of the first kind obey the recurrence relation

\left[{\begin{matrix}n+1\\k\end{matrix}}\right]=\left[{\begin{matrix}n\\k-1\end{matrix}}\right]-n\left[{\begin{matrix}n\\k\end{matrix}}\right]

for $1\leq k\leq n-1$ , with the initial conditions

\left[{\begin{matrix}n\\0\end{matrix}}\right]=0\quad {\mbox{ and }}\quad \left[{\begin{matrix}1\\1\end{matrix}}\right]=1

The above follows from the recurrence relation on the falling factorials:

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

Simple identities

Note that

\left[{\begin{matrix}n\\1\end{matrix}}\right]=(-1)^{n-1}(n-1)!

and

\left[{\begin{matrix}n\\n\end{matrix}}\right]=1

and

\left[{\begin{matrix}n\\n-1\end{matrix}}\right]=(-1)^{n}{n \choose 2}

Other relations include

\left[{\begin{matrix}n\\2\end{matrix}}\right]=(-1)^{n}(n-1)!\;H_{n-1}

and where $H_{n}$ is a harmonic number and

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

where $H_{n}^{(m)}$ is a generalized harmonic number. A generalization of this relation th harmonic numbers is given in a later section.

Generating function

A variety of identities may be derived by manipulating the generating function

(1+t)^{x}=\sum _{n=0}^{\infty }{x \choose n}t^{n}=\sum _{n=0}^{\infty }{\frac {t^{n}}{n!}}\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]x^{k}=\sum _{k=0}^{\infty }x^{k}\sum _{n=k}^{\infty }{\frac {t^{n}}{n!}}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{x\ln(1+t)}

In particular, the order of summation may be exchanged, and derivatives taken, and then t or x may be fixed.

Finite sums

A simple sum is

\sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=(-1)^{n}n!

Infinite sums

Some infinite sums include

\sum _{n=m}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {x^{n}}{n!}}={\frac {\left(\ln(1+x)\right)^{m}}{k!}}

which holds for $x<1$ .

Relation to harmonic numbers

Stirling numbers of the first kind can be expressed in terms of the harmonic numbers as follows:

s(n,k)=(-)^{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, $\Gamma (x)$ is the Gamma function and $H_{n}^{(m)}$ is the harmonic number.

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:

|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$ object with $k$ cycles, and label the objects $a_{1},\ldots ,a_{n}$ , so that the permutation is represented by

\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{\mbox{ 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.

Stirling numbers of the second kind

Stirling numbers of the second kind S(n,k) (with a capital "S") count the number of equivalence relations having k equivalence classes defined on a set with n elements. The sum

B_{n}=\sum _{k=1}^{n}S(n,k)

is the nth Bell number. If we let

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

(in particular, (x)₀ = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by

\sum _{k=0}^{n}S(n,k)(x)_{k}=x^{n}.

(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.)