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