Recurrence formula

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

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

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

To calculate the number of elements in the first block, note that the deletion of $\{n\}$ in each of the partitions would result in a set of partitions that is exactly describing the number of ways one can partition $\left\{1,\cdots,n-1\right\}$ into $k-1$ blocks, or in other words ${n-1}\brace{k-1}$. Now note that the deletion of $\{n\}$ did not, in any way, change the number of partitions in block one. It follows that the cardinality of the first block is ${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 $\{n\}$ in each of the partitions, this time locate the block in each partition that contains $n$. From this block, erase $n$. Notice that this time we have not changed $k$ but have reduced each block in the partition to a partition of $n-1$. But, there is multiplicity in these blocks. Exactly how many are there? A quick argument shows that each new partiton of $n-1$ will be repeated $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 $k{{n-1}\brace{k}}$.

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

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

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

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

Basically $\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. ${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, $b_{n}$, is the number of ways to partition a set of n objects into subsets.

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

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

The exponential generating function for the Bell number is

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

The general formula is $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, $b_{n}$, is the number of ways to partition a set of n objects into subsets.

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

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

The exponential generating function for the Bell number is

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

The general formula is $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)