Math Help - Recurrence formula

1. Recurrence formula

1. Let $u(n)$ denote the number of ways in which a set of $\mbox{n}$ elements can be partitioned into non-empty subsets. For example, $u(3)=5$, corresponding to:

$\{a,b,c\}$

$\{a,b\}, \{c\}$

$\{a,c\},\{b\}$

$\{a\},\{b,c\}$

$\{a\},\{b\},\{c\}$

How do I do this?

2. Originally Posted by usagi_killer
1. Let $u(n)$ denote the number of ways in which a set of $\mbox{n}$ elements can be partitioned into non-empty subsets. For example, $u(3)=5$, corresponding to:

$\{a,b,c\}$

$\{a,b\}, \{c\}$

$\{a,c\},\{b\}$

$\{a\},\{b,c\}$

$\{a\},\{b\},\{c\}$

How do I do this?
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.

3. Originally Posted by usagi_killer
1. Let $u(n)$ denote the number of ways in which a set of $\mbox{n}$ elements can be partitioned into non-empty subsets. For example, $u(3)=5$, corresponding to:

$\{a,b,c\}$

$\{a,b\}, \{c\}$

$\{a,c\},\{b\}$

$\{a\},\{b,c\}$

$\{a\},\{b\},\{c\}$

How do I do this?
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

4. P.S. If you want me to show you how to do the generating function, just let me know.

5. 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

6. 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.

7. 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.

8. Thank you guys, I really appreciate the help, I understand how to do this question now

9. 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?