Hello, I'd be really grateful for any help with this problem:

Show that the number of partitions of the set $\displaystyle \{1,...,n\}$, such that no two consecutive integers appear in the same block of a partition is the Bell number $\displaystyle B_{n-1}$.

***

We know that the number of partitions of an $\displaystyle n$-element set is $\displaystyle B_n$. For example, if we have a 3-element set $\displaystyle \{1,2,3\}$ then ALL possible partitions of that set would be

$\displaystyle \{\{1,2,3\}\};\{\{1,2\},\{3\}\};\{\{1,3\},\{2\}\}; \{\{2,3\},\{1\}\};\{\{1\},\{2\},\{3\}\}$

and therefore $\displaystyle B_3=5$. 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 $\displaystyle \{\{1,3\},\{2\}\}$ and $\displaystyle \{\{1\},\{2\},\{3\}\}$ - there are two of them, which is exactly the second Bell number, $\displaystyle B_2$, and in fact there are only two partitions of a 2-element set, say, $\displaystyle \{1,2\}$; the first one is $\displaystyle \{\{1,2\}\}$ and the second one is $\displaystyle \{\{1\},\{2\}\}$.

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 $\displaystyle B_2$. But, how to give a combinatorial proof that the number of such partitions of a $\displaystyle n$-element set is $\displaystyle B_{n-1}$?

Many thanks!