Onto Functions and Stirling NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/