Problem: given a set of elements in ow many ways can one partition the set into non-empty subsets.
Originally Posted by usagi_killer
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.
P.S. If you want me to show you how to do the generating function, just let me know.
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 :D
Maybe just a push so that we can try it out first - I really do not know much about generating functions.
Originally Posted by Drexel28
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.
Thank you guys, I really appreciate the help, I understand how to do this question now :)
Just a flourish of the hands and some prestidigitation and this generating function appeared, huh? (Smirk)
Originally Posted by galactus