1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:
How do I do this?
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.
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
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
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.