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 elements in ow many ways can one partition the set into non-empty subsets.
Solution: Let us denote as the number of ways we can parition into blocks. Clearly, then the number of ways we can partition the set is .
Let us first begin by finding a recurrence relation for . To do this let . Partition into two blocks, namely: those elements such that and those elements such that . Since it follows that the sum of the cardinality of the two blocks must be equal to .
To calculate the number of elements in the first block, note that the deletion of in each of the partitions would result in a set of partitions that is exactly describing the number of ways one can partition into blocks, or in other words . Now note that the deletion of did not, in any way, change the number of partitions in block one. It follows that the cardinality of the first block is .
To calculate the number of elements in the second block we employ a similar method. Instead of this time erasing in each of the partitions, this time locate the block in each partition that contains . From this block, erase . Notice that this time we have not changed but have reduced each block in the partition to a partition of . But, there is multiplicity in these blocks. Exactly how many are there? A quick argument shows that each new partiton of will be repeated times. Thus, since the deletion method we used did not change the cardinality of the second block we may conclude that the cardinality is .
It immediately follows that .
To make a valid sequence for a fixed positive we must make the convention (which in no way affects the problem at hand) that , , and . Now our recurrence relation is legitimate over all .
An almost immediate consequence of of the way we defined is that since the only way to partition into blocks is and the only way to parition into block is . So in your example we'd need to calculate , but since we must only compute . But, by our recurrence relation we see that . So then
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 =
where,
recursion equation is
Basically 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. 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, , is the number of ways to partition a set of n objects into subsets.
You already have as an example.
The sequence of Bell numbers is
The exponential generating function for the Bell number is
. This can be derived by using
The general formula is
Note the formula looks a whole lot like the MacLaurin series for e, huh?.
With some effort, these can be derived.