Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Whoops, thanks for fixing the spelling. –  Clara Jan 29 '12 at 21:42
add comment

1 Answer 1

up vote 4 down vote accepted

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}.

share|improve this answer
1  
Ah right! Thanks for pointing this out. :) –  Clara Jan 29 '12 at 22:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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