Partitioning ElementsDate: 12/10/2001 at 12:56:47 From: Rajshree Pawar Subject: Discrete Math Resp. Sir, I used the formula. m T(n,m) = SUM[(-1)^k*C(m,k)*(m-k)^n] k=0 obtained from your archives to the following question but was unable to solve it. Kindly help me with this problem. If Part(n, k) is the number of ways to partition a set of n elements into k subsets a) What is Part(5,2)? b) Prove that Part(n+1, k) = Part(n, k-1) + k*Part(n,k). Date: 12/11/2001 at 06:10:32 From: Doctor Mitteldorf Subject: Re: Discrete Math Dear Rajshree, It's all there in Doctor Anthony's explanation of the T function: http://mathforum.org/dr.math/problems/amal2.2.3.00.html but the subject can be confusing, especially if English is not your first language. Doctor Anthony's T function is the same as the Part function that you are asked about. If you calculate some examples, you can get enough familiarity with it to feel comfortable, and the exercise you're given is a very good start. Let's begin with part (b): How to compute Part(n+1,k)? To add one more object to an existing partition, there are two possibilities: First, you can partition n objects into k subsets. Then take the (n+1st) object and add it to any one of the subsets you've got. So the number of possibilities we get this way is k*Part(n,k). Second, you can put that (n+1st) object in a subset all of its own. The number of ways to do this is the number of ways to partition the remaining n objects into (k-1) subsets, which, by definition is Part(n,k-1). This equation, derived for (b), is a sufficient prescription for calculating the Part function. You could write a computer program that defines Part(n,k) recursively in terms of itself. It only remains to terminate the recursion, by noting that the number of ways to partition n things into n subsets is 1. For part (a) you are asked to compute Part(5,2) explicitly. I suggest you do this in three ways: First, by logic: accounting for all the possibilities. I'll guide you through this calculation. Second, list all the possibilities explicitly: A BCDE, B ACDE etc. AB CDE AC BDE etc. Third, use the recursive definition to follow Part(5,2) back to smaller numbers: Part(5,2) = Part(4,1) + 2*Part(4,2) Part(4,2) = Part(3,1) + 1*Part(4,1) --------------------------------------------------- Now, I promised to go through the calculation of Part(5,2) with pure logic. There are two possibilities: You can partition the 5 into 4-1 or into 3-2. There are 5 ways to do 4-1, since you simply need to decide which of the 5 will be by itself. There are C(5,2) ways to do 3-2, because choosing which pair will be the two, the rest is determined. So the answer must be 5+10 = 15. So, now it's your turn. List all 15 possibilities, then calculate Part(5,2) from the recursive formula. - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 12/10/2001 at 14:55:54 From: Doctor Anthony Subject: Re: Discrete Math P(n+1,k)= k[P(n,k)] + P(n,k-1) What you describe here are Stirling numbers of the second kind. I will illustrate the recurrence relation with actual numbers to make the reasoning clearer. P(n+1,k) = k[P(n,k)] + P(n,k-1) For example P(5,3) = 3[P(4,3)] + P(4,2) Think of this as the number of ways of distributing 5 objects into 3 indistinguishable cells so that no cell is empty. If we have already distributed 4 objects into 3 cells, then the 5th object can be placed in one of the cells in 3 ways. This gives 3[P(4,3)] Alternatively, the chosen cell was empty and the other 4 had been distributed in P(4,2) ways. (This is okay because we are concerned that there is no empty cell AFTER the 5th ball has been placed.) It follows that P(5,3) = 3[P(4,3)] + P(4,2) This is a particular case of the recurrence relation we are required to prove. The above argument is applicable to the general case of n and k so we get: P(n+1,k) = k[P(n,k)] + P(n,k-1) - 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/