Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/