# Partitions of $\{1,\dots,n\}$ with no consecutive integers in each block is counted by $B(n-1)$?

I'm trying to understand why $B(n-1)$ also counts the number of partitions of $[n]$ where not two consecutive integers appear in the same block.

Now the bell number $B(n-1)$ counts the number of partitions of the $n-1$-set $[n-1]$. Suppose I take any partition $\pi$ of $[n-1]$. Now taking $i,i+1,\dots,j$ to be a maximal sequence of two or more consecutive integers in a block, I can remove alternating integers $j-1$, $j-3$, $j-5$,... and put them in a block with $n$. Doing so for all sequences of consecutive integers in blocks of $\pi$ will then give a partition of $[n]$ with no two consecutive numbers.

I think this gives a needed bijection of the two things, but if I'm given a partition of $[n]$ with no two consecutive integers in a block, how can I reconstruct the partition of $[n-1]$ to see that it is indeed a bijection?

Thanks!

-
Whoops, thanks for fixing the spelling. – Clara Jan 29 '12 at 21:42

The relation you give is indeed a bijection! To reconstruct the original partition of $[n-1]$, take every element $j \neq n$ in the same block as $n$ and put it in the block containing $j+1$.