Finding the number of partitions without consecutive integers in each block
Hello, I'd be really grateful for any help with this problem:
Show that the number of partitions of the set , such that no two consecutive integers appear in the same block of a partition is the Bell number .
We know that the number of partitions of an -element set is . For example, if we have a 3-element set then ALL possible partitions of that set would be
and therefore . But in our problem, we are interested only in those partitions of a set which consist of blocks without any consecutive integers. So, in the above example, we would only be interested in partitions and - there are two of them, which is exactly the second Bell number, , and in fact there are only two partitions of a 2-element set, say, ; the first one is and the second one is .
Here, we have shown that the number of partitions of a 3-element set such that there are no consecutive integers in any block is . But, how to give a combinatorial proof that the number of such partitions of a -element set is ?
Many thanks! :)