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