given a set of elements in ow many ways can one partition the set into non-empty subsets.Problem:

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

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.