# Recurrence formula

• Dec 18th 2009, 06:33 PM
usagi_killer
Recurrence formula
• Dec 18th 2009, 11:56 PM
Drexel28
Problem: given a set of $\displaystyle n$ elements in ow many ways can one partition the set into non-empty subsets.

Solution: Let us denote $\displaystyle {n}\brace{k}$ as the number of ways we can parition $\displaystyle \left\{1,\cdots,n\right\}$ into $\displaystyle k$ blocks. Clearly, then the number of ways we can partition the set is $\displaystyle \sum_{k=1}^{n}{{n}\brace{k}}$.

Let us first begin by finding a recurrence relation for $\displaystyle {n}\brace{k}$. To do this let $\displaystyle S_k=\left\{P:P\text{ is a partition of }\left\{1,\cdots,n\right\}\text{ into }k\text{ blocks}\right\}$. Partition $\displaystyle S_k$ into two blocks, namely: those elements such that $\displaystyle \{n\}\in P$ and those elements such that $\displaystyle \{n\}\notin P$. Since $\displaystyle \left|S_k\right|={{n}\brace{k}}$ it follows that the sum of the cardinality of the two blocks must be equal to $\displaystyle {n}\brace{k}$.

To calculate the number of elements in the first block, note that the deletion of $\displaystyle \{n\}$ in each of the partitions would result in a set of partitions that is exactly describing the number of ways one can partition $\displaystyle \left\{1,\cdots,n-1\right\}$ into $\displaystyle k-1$ blocks, or in other words $\displaystyle {n-1}\brace{k-1}$. Now note that the deletion of $\displaystyle \{n\}$ did not, in any way, change the number of partitions in block one. It follows that the cardinality of the first block is $\displaystyle {n-1}\brace{k-1}$.

To calculate the number of elements in the second block we employ a similar method. Instead of this time erasing $\displaystyle \{n\}$ in each of the partitions, this time locate the block in each partition that contains $\displaystyle n$. From this block, erase $\displaystyle n$. Notice that this time we have not changed $\displaystyle k$ but have reduced each block in the partition to a partition of $\displaystyle n-1$. But, there is multiplicity in these blocks. Exactly how many are there? A quick argument shows that each new partiton of $\displaystyle n-1$ will be repeated $\displaystyle k$ times. Thus, since the deletion method we used did not change the cardinality of the second block we may conclude that the cardinality is $\displaystyle k{{n-1}\brace{k}}$.

It immediately follows that $\displaystyle {{n}\brace{k}}={{n-1}\brace{k-1}}+k{{n-1}\brace{k}}$.

To make $\displaystyle f_k(n)={{n}\brace{k}}$ a valid sequence for a fixed positive $\displaystyle k$ we must make the convention (which in no way affects the problem at hand) that $\displaystyle {{n}\brace{k}}=0,\text{ }n<k$, $\displaystyle {{0}\brace{0}}=0$, and $\displaystyle {{{n}\brace{0}}},\text{ }n\ne0$. Now our recurrence relation is legitimate over all $\displaystyle n\in\mathbb{N}$.

An almost immediate consequence of of the way we defined $\displaystyle {n}\brace{k}$ is that $\displaystyle {{n}\brace{n}}={{n}\brace{1}}=1$ since the only way to partition $\displaystyle \left\{1,\cdots,n \right\}$ into $\displaystyle n$ blocks is $\displaystyle \{1\},\cdots,\{n\}$ and the only way to parition $\displaystyle \left\{1,\cdots,n\right\}$ into $\displaystyle 1$ block is $\displaystyle \{1,\cdots,n\}$. So in your example we'd need to calculate $\displaystyle \sum_{k=1}^{3}{{3}\brace{k}}$, but since $\displaystyle {{3}\brace{1}}={{3}\brace{3}}=1$ we must only compute $\displaystyle {3}\brace{2}$. But, by our recurrence relation we see that $\displaystyle {{3}\brace{2}}={{2}\brace{1}}+2{{2}\brace{2}}=1+2= 3$. So then $\displaystyle \sum_{k=1}^{3}{{3}\brace{k}}=1+3+1=5$

Remark: I could take this even further and find a generating function for this problem, but I believe that you should give it a try on your own.
• Dec 19th 2009, 12:03 AM
aman_cc
Hi - Here is an attempt

Number of ways = $\displaystyle \sum_{i=1}^{n}\theta(n,i)$

where,
recursion equation is
$\displaystyle \theta(n,i) = \theta(n-1,i)i+\theta(n-1,i-1)$
$\displaystyle \theta(n,1)=1$

Basically $\displaystyle \theta(n,i)$ is number of ways to divide n elements in i groups.

I might have complicated it. But this looks most straight fwd to me. Haven't been able to work out a closed from formula.
Let me know if you need more inputs on how I came up with the recuursive definition.
Thanks
• Dec 19th 2009, 03:28 AM
Drexel28
P.S. If you want me to show you how to do the generating function, just let me know.
• Dec 19th 2009, 04:52 AM
Isomorphism
This problem can be solved by adding up a popular function called Stirling number. $\displaystyle {n}\brace{k}$ in #2 is a notation for Stirling number of the second kind. You might find this article useful :D
• Dec 19th 2009, 06:41 AM
aman_cc
Quote:

Originally Posted by Drexel28
P.S. If you want me to show you how to do the generating function, just let me know.

Maybe just a push so that we can try it out first - I really do not know much about generating functions.
• Dec 19th 2009, 07:44 AM
galactus
This is an interesting topic.

The nth Bell number, $\displaystyle b_{n}$, is the number of ways to partition a set of n objects into subsets.

You already have $\displaystyle b_{3}=5$ as an example.

The sequence of Bell numbers is $\displaystyle 1,1,2,5,15,52,.....$

The exponential generating function for the Bell number is

$\displaystyle e^{e^{x}-1}$. This can be derived by using $\displaystyle b_{n+1}=\sum_{k=0}^{\infty}\frac{k^{n-1}}{(k-1)!}$

The general formula is $\displaystyle b_{n}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^{n}}{k !}$

Note the formula looks a whole lot like the MacLaurin series for e, huh?.

With some effort, these can be derived.
• Dec 19th 2009, 05:47 PM
usagi_killer
Thank you guys, I really appreciate the help, I understand how to do this question now :)
• Dec 19th 2009, 09:21 PM
Drexel28
Quote:

Originally Posted by galactus
This is an interesting topic.

The nth Bell number, $\displaystyle b_{n}$, is the number of ways to partition a set of n objects into subsets.

You already have $\displaystyle b_{3}=5$ as an example.

The sequence of Bell numbers is $\displaystyle 1,1,2,5,15,52,.....$

The exponential generating function for the Bell number is

$\displaystyle e^{e^{x}-1}$. This can be derived by using $\displaystyle b_{n+1}=\sum_{k=0}^{\infty}\frac{k^{n-1}}{(k-1)!}$

The general formula is $\displaystyle b_{n}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^{n}}{k !}$

Note the formula looks a whole lot like the MacLaurin series for e, huh?.

With some effort, these can be derived.

Just a flourish of the hands and some prestidigitation and this generating function appeared, huh? (Smirk)