7
$\begingroup$

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!

  • 0
    Whoops, thanks for fixing the spelling.2012-01-29

1 Answers 1

8

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
    Ah right! Thanks for pointing this o$u$t. :)2012-01-29