Associated Topics || Dr. Math Home || Search Dr. Math

### Stirling Numbers

```
Date: 05/26/99 at 05:58:31
From: John C. Westmoreland
Subject: Evaluate Stirling Numbers of the First and Second Kinds

Hello Dr. Math,

I need some practical examples of how to evaluate Stirling Numbers of
the First and Second Kinds. So far, I'm not satisfied with what I've
found regarding the formulas and the practical examples.

Thanks in advance for any help,
John W.
```

```
Date: 05/26/99 at 16:21:01
From: Doctor Anthony
Subject: Re: Evaluate Stirling Numbers of the First and Second Kinds

Stirling Numbers of the Second and First Kind
----------------------------------------------
These numbers relate to the number of ways of distributing objects
into cells.  There are various conditions to be considered as follows:

(1) distinct objects into distinct cells
(2) distinct objects into identical cells
(3) indistinguishable objects into distinct cells
(4) indistinguishable objects into identical cells
(5) distinct objects into distinct cells in which the order within a
cell matters
(6) distinct objects into identical cells and circular order within a
cell matters

Suppose we have n numbered balls and m numbered cells, with n > m.
Then the function T(n,m) is the number of ways we can distribute the
balls into the cells such that no cell is empty.

The required result is given by

n!
SUM[-----------------] ...........(1)    [= T(n,m)]
n1!n2!n3!...n(m)!

n1 = number of objects in cell(1), n2 = number of objects in cell(2),
etc.

where the sum is taken over all solutions of:

n1 + n2 + n3 + ..... + n(m) = n   [and n(i) NOT = 0]

With no cell empty expression (1) is denoted by  T(n,m)

3!       3!
For example  T(3,2) = ------ + ------  =  3 + 3 = 6
1! 2!    2! 1!

4!          4!         4!
T(4,3) = -------  + -------- + --------  = 12 + 12 + 12 = 36
1! 1! 2!   1! 2! 1!    1! 1! 2!

We have the following recurrence relation:

T(n,m) = m[T(n-1,m-1) + T(n-1,m)]

For example  T(5,3) = 3[T(4,2) + T(4,3)]

Think of this as the number of ways of distributing 5 objects into 3
cells so that no cell is empty.

If we have already distributed 4 objects then the 5th object can be
placed in one of the cells in 3 ways.  Then there are two situations
to consider.

The chosen cell was empty and the other 4 had been distributed in
T(4,2) ways. (This is OK because we are concerned that there is no
empty cell AFTER the 5th ball has been placed.)

The chosen cell was occupied and the other 4 must then have been
distributed in T(4,3) ways.

It follows that  T(5,3) = 3[T(4,2) + T(4,3)]

The formula for T(n,m) is also given by the summation

m
T(n,m) = SUM[(-1)^k.C(m,k).(m-k)^n]
k=0

Example  T(5,3) = 3^5 - 3(2^5) + 3(1^5) = 243 - 96 + 3 = 150

The proof of this result follows directly from the inclusion-exclusion
principle.

Inclusion-Exclusion Principle
------------------------------
It is easy to illustrate the principle with two or three probabilities
using a Venn diagram.

For example with two overlapping probabilities P(A), P(B), we have

P(A or B) = P(A) + P(B) - P(A and B)

The overlapping region is added in with P(A) and added in again with
P(B), so to get it added in once only we subtract it, giving rise to
the expression shown above.

With three overlapping probabilities P(A), P(B) and P(C) we get

P(A or B or C) = P(A) + P(B) + P(C)
- P(A and B) - P(B and C) - P(C and A)
+ P(A and B and C)

now the overlap of all 3 probabilities is added in 3 times by the
first line of this equation, subtracted 3 times by the second line of
the equation and so must be added in again by the third line.

The area corresponding to A and B BUT NOT C is added in twice in the
first line and subtracted once in the second line, so it will appear
once as is required. Similarly for area B and C but not A, and the
area corresponding to C and A but not B, each will eventually appear
once only.

With more probabilities the pattern continues and the proof by
induction is not difficult but a little tedious. The name 'inclusion-
exclusion' describes exactly what is happening. Regions are being
added a number of times and subtracted a number of times in such a way
that each region occurs exactly once.

Suppose we let |A| be the number of ways that cell(1) is empty, |B| is
the number of ways that cell(2) is empty and |C| is the number of ways
that cell (3) is empty. |U| is the universal set and is the total
number of ways of distributing 5 different objects into 3 cells,
(=3^5).

If   S(0) = |U|
S(1) = |A| + |B| + |C|
S(2) = |AB| + |BC| + |CA|
s(3) = |ABC|

Then |A'B'| = S(0) - S(1) + S(2)
|A'B'C'| = S(0) - S(1) + S(2) - S(3)

(which means that none of cell(1), cell(2) or cell(3) is empty)

and clearly this idea can be extended to any number of cells.

The general formula is:

m
|A'B'C'D'E'......M'| =  SUM[(-1)^k.S(k)]
k=0

Which is the formula for T(n,m) quoted above.

Example:

Find  T(5,3)

We have S(0) = 3^5 = 243    S(1) = 2^5 + 2^5 + 2^5 = 96

S(2) = 1 + 1 + 1    S(3) = 0

and applying the formula for inclusion exclusion we get

|A'B'C'| = 243 - 96 + 3 - 0 = 150   as we found before.

The general formula to use for n objects and m cells is:

m
T(n,m) = SUM[(-1)^k.C(m,k).(m-k)^n]
k=0

From here to Stirling Numbers of the Second Kind is a very easy step.
We simply remove the condition that the cells are numbered.  This
means that we could permute the cells in m! ways without giving rise
to a new distribution and so T(n,m) is too large by a factor of m!
when we remove the identity numbers from the cells.  And so we have
the formula for Stirling Numbers of the Second Kind

S(n,m) = T(n,m)/m!

This is the number of ways of distributing n distinct objects into m
identical cells such that no cell is empty.

Stirling Numbers of the First Kind
-----------------------------------
In general S1(n,m) is the number of ways to partition n objects into m
(non-empty) parts and arrange the members of each part around a
circle. The order of the objects around each circle must be taken into
account.

The generating function for S1(n,m) is the coefficient of x^m in the
expansion of x(x-1)(x-2)....(x-n+1)

The numbers satisfy the recurrence relation

S1(n+1,r) = S1(n,r-1) + n.S1(n,r)

We have  S1(n,1) = (n-1)!
S1(n,n) = 1
S1(n,n-1) = C(n,2)

We get the following table using the recurrence relation:

r
|   1    2    3    4    5    6 ....
------|-------------------------------------
1   |   1
2   |   1    1
n  3   |   2    3    1
4   |   6   11    6    1
5   |  24   50   35   10    1
6   | 120  274  225   85   15    1

And using the generating function, S1(5,2)

is the coefficient of  x^2 in  x(x-1)(x-2)...(x-5+1)
= x(x-1)(x-2)(x-3)(x-4)

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

and we can see that the |coefficient| of x^2 is 50.

The other coefficients also give the required terms in row 5 of above
table.

Example.
--------
In how many ways can six people be seated round 3 identical tables if
there is at least one person at each table?

From the above table we find   S1(6,3) = 225

To get the recurrence relation from first principles, suppose we have
distributed 5 people in S1(5,2) or S1(5,3) ways. That is, all five are
at all 3 tables or at only 2 tables, and we then add a sixth person.
If they are only at two tables then the 6th person MUST go to the
empty table. He can be placed in 1 way, and we get a term  S1(5,2) in
this situation. If the 5 people are distributed at 3 tables there will
be 5 gaps that the extra person could occupy, and so the contribution
in this situation to the new total will be  5 x S1(5,3).

It follows that   S1(6,3) = S1(5,2) + 5 x S1(5,3)

Check from table above:

S1(5,2) + 5 x S1(5,3)

50 + 5 x 35  =  225  =  S1(6,3)

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 05/26/99 at 20:05:50
From: John C. Westmoreland
Subject: Re: Evaluate Stirling Numbers of the First and Second Kinds

Dr. Math,

I'll go through this and see if I can apply it to the algorithm I'm
attempting to solve. I'll let you know the outcome.

Thanks for responding so quickly!
John
```
Associated Topics:
College Number Theory
High School Number Theory
High School Permutations and Combinations
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search