Thread: 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!

Let be the number of partitions of into classes such that no 2 consecutive integers are in the same class.

We'll see that: holds.

Indeed, the first term corresponds to the number of cases in which lives alone in its own class, otherwise, if we have built a partition of into classes where no 2 integers in a same class are consecutive, the number may be placed in of them, since it can't go where is.

From there we get where are the Stirling numbers of the second kind (*)


Now we directly sum over k:


(*)


Sum:

Thus: where (considering the initial values)

From there: and since

It follows: (in the same way we can get the Generating function for the Stirling numbers of the second kind)

Thus:

Thanks a million, PaulRS!

Your post has been extremely helpful and illuminating.