Stirling numbers

Posted on May 12, 2009 by amca01

From my perspective as a tertiary mathematics educator, Stirling numbers are the poor cousins of the binomial coefficients. In spite of their many and various applications, they would rarely make a mention in a general undergraduate syllabus, possibly only in a combinatorics subject, and maybe not even then.

Stirling numbers exist in two forms: numbers of the first kind, and of the second kind. They are very closely connected. Interestingly, there are several different definitions, depending on who you read, and on what computer algebra system you use. For example, Sage:

sage: stirling_number1(6,3)
225

But Maxima:

(%i1) stirling1(6,3);
(%o1) - 225

Maple also gives the number with a negative sign. So, is the value 225 or -225? Well, again, it depends on your definition. But first, some notation. Following Knuth (“Two notes on notation”, American Mathematical Monthly, Volume 99, Issue 5 (May 1992) pages 403 – 422; a copy of the \TeX source is available here), we write

\displaystyle{\left[{n\atop k}\right]}

for the Stirling numbers of the first kind, and

\displaystyle{\left\{{n\atop k}\right\}}

for the Stirling numbers of the second kind.

One definition of the Stirling numbers of the first kind is that they are the coefficients in the expansion of

x(x-1)(x-2)(x-3)\cdots(x-n+1)

So for n=5, for example, we have

x(x-1)(x-2)(x-3)(x-4)=x^5 - 10x^4 + 35x^3 - 50x^2 + 24x

and the numbers [1,-10, 35, -50, 24, 0] are the Stirling numbers of the first kind for n=5. That is, we can write

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

The expression

x(x-1)(x-2)(x-3)\cdots(x-n+1)

is called a falling factorial, and is denoted (x)_n. Thus we have

\displaystyle{(x)_n=\sum_{k=1}^n\left[{n\atop k}\right]x^k.}

The Stirling numbers of the second kind may be defined by

\displaystyle{x^n=\sum_{k=1}^n\left\{{n\atop k}\right\}(x)_k.}

These two generating formulas have a nice dual relationship – in each one, the power (or falling factorial) is expressed in terms of the other, with Stirling numbers as coefficients. Using this definition, the Stirling numbers of the first kind alternate in sign.

Other writers and users of the Stirling numbers prefer all of them to be positive. For this definition we can use the rising factorial

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

to generate Stirling numbers of the first kind. If all these numbers are positive, we have a simple combinatorial definition: the number

\displaystyle{\left[{n\atop k}\right]}

is the number of permutations of n numbers which can be expressed with exactly k cycles. For this reason Knuth recommends the number be spoken as “n cycle k”. Here are the 11 ways in which 4 numbers can be expressed as two cycles:


[1, 2, 3][4], [1, 3, 2][4], [1, 2, 4][3], [4, 2, 1][3],
[1, 3, 4][2], [4, 3, 1][2], [2, 3, 4][1], [4, 3, 2][1]
[1, 2][3, 4], [1, 3][2, 4], [1, 4][2, 3]

The Stirling numbers of the second kind also have a combinatorial interpretation:

\displaystyle{\left\{{n\atop k}\right\}}

is the number of ways a set of n elements can be partitioned into k subsets, and so the number can be spoken as “n subset k”. Here are the 15 ways in which a 5 element set can be split up into two subsets:


{1, 2, 3, 4}{5}, {1, 2, 3, 5}{4}, {1, 2, 4, 5}{3}
{1, 3, 4, 5}{2}, {2, 3, 4, 5}{1}, {1, 2, 3}{4, 5}
{1, 2, 4}{3, 5}, {1, 2, 5}{3, 4}, {1, 3, 4}{2 ,5}
{1, 3, 5}{2, 4}, {1, 4, 5}{2, 3}, {2, 3, 4}{1, 5}
{2, 3, 5}{1, 4}, {2, 4, 5}{1, 3}, {3, 4, 5}{1, 2}

With either the generating functions or the combinatorial interpretations the following recursions are easy to prove:

\displaystyle{\left[{n\atop k}\right]=(n-1)\left[{n-1\atop k}\right]+\left[{n-1\atop k-1}\right]},

\displaystyle{\left\{{n\atop k}\right\}=k\left\{{n-1\atop k}\right\}+\left\{{n-1\atop k-1}\right\}}.

Given the confusion between the exact definition of the Stirling numbers of the first kind, it should be noted that Stirling himself only used the numbers in positive form, and for him the numbers of the first kind (given as his “second table”) arose in conjunction with the summation of infinite series, so that, in modern notation:

\displaystyle{\frac{1}{z^m}=\sum_{k=m}^{\infty}\frac{\left[{k\atop m}\right]}{z(z+1)(z+2)\cdots (z+k)}}

Stirling doesn’t give the recurrences, nor the combinatorial interpretations.

One book which treats the Stirling numbers in considerable detail, and discusses many relationships between them, is Knuth et al’s Concrete Mathematics.

Filed under: Maths teaching

« »

One Response

  1. Marie, on May 13th, 2009 at 12:17 am Said:

    Yes! It’s right! There are 2 definition of the Stirling numbers of the first kind. The non signed Stirling numbers of the first kind and the Stirling numbers of the first kind.
    Thanks for explanation about different definition in CAS.

    Reply

Leave a Reply