Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search