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?


  • $\begingroup$ Whoops, thanks for fixing the spelling. $\endgroup$ – 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$.

Example: let's say you perform your function and arrive at the non-consecutive partition

{1,3,6}, {5}, {2,4,7}.

From your specification of how to choose which numbers to remove from the original blocks, you know that 2 was removed from a block containing 3, so put 2 back in the block {1,3,6}. Similarly, you know 4 was taken from the block containing 5, so put 4 back in the block {5}. Finally, just take out 7 entirely, and you're left with the original partition: {1,2,3,6}, {4,5}.

  • 1
    $\begingroup$ Ah right! Thanks for pointing this out. :) $\endgroup$ – Clara Jan 29 '12 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.