Partitioning Elements

Date: 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/