Onto Functions and Stirling Numbers

Date: 09/22/2002 at 23:51:10
From: Tom
Subject: Onto Functions and Stirling Numbers

Hello Dr. Math,

I don't know if you can help me with this question but how would I 
show for m >= 3

   s(m, m-2) = (1/24)m(m-1)(m-2)(3m-1)

where s(m,n) are referred to as the Stirling numbers of the first 
kind?

Is there a formula for the Stirling numbers of the first kind that I 
could use?

Thank you.

Date: 09/23/2002 at 13:06:47
From: Doctor Anthony
Subject: Re: Onto Functions and Stirling Numbers

We use S(n,m) to denote Stirling Numbers of the First Kind. It 
represents the number of ways to seat n people at m circular tables 
with at least one person at each table. The arragements at any one 
table are not distinguished if one can be rotated into another. 
The ordering of the tables is NOT taken into account. Briefly, 
these numbers count the number of arrangements of n objects into 
m non-empty circular permutations.

The generating function for S(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

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

We have  S(n,1) = (n-1)!
         S(n,n) = 1
         S(n,n-1) = C(n,2)  (select 2 persons for one table)

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, S(5,2)

is 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 |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   S(6,3) = 225

To get the recurrence relation from first principles, suppose we have 
distributed 5 people in S(5,2) or S(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 only at two tables, then the 6th person MUST go to the empty table.  
He could be placed in one way and we get a term S(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 is  5 x S(5,3).

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

Check from the table above:

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

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

Now turning to your question, we are asked to show

  S(m,m-2) = (1/24)m(m-1)(m-2)(3m-1)

We showed earlier that S(m,m-1) = C(m,2)

That is, we have m people and have to select two to sit together at 
one of the tables.  It does not matter which table, and with just two 
at the table you cannot change the order.

For S(m,m-2) we have m-2 tables and m people.  We could have 3 at one 
table and 1 at each of the other tables. The 3 persons are chosen in 
C(m,3) ways and they can be arranged in 2 ways at the table.  This 
gives 2 x C(m,3) arrangements.  Alternatively we could have 2 at two 
tables and 1 at each of the other tables.  This could be done in 
C(m,4) x C(4,2)/2 ways.  

Notice that we divide by 2 because the number of WAYS of dividing 4 
into 2 groups of 2 is C(4,2)/2, since when we select 2 that 
automatically selects the other 2.

Combining these answers we get

 S(m,m-2) = 2 x C(m,3) + C(m,4) x C(4,2)/2

             2 x m(m-1)(m-2)     m(m-1)(m-2)(m-3)x 3
          = ----------------- + --------------------
                   3!                   4!   

             m(m-1)(m-2)[8 + 3(m-3)]
          =  -----------------------
                       24

             m(m-1)(m-2)(3m-1)
          = -------------------
                    24

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