Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

As everyone knows, the Bell number $B(n)$ is the number of ways to partition a set of size $n$. Equivalently, it is the number of ways $n$ numbered balls can be put into $n$ identical boxes. On the other hand, the number of ways to put $n$ identical balls into $n$ numbered boxes is $C(n)=\binom{2n-1}{n}$. For $n<10$ we have $B(n)\lt C(n)$ and for $n\ge 10$ we have $B(n)\gt C(n)$. The question is why does this switch occur at $n=10$. Is there a combinatorial explanation?

share|improve this question
1  
I doubt it. What would such an explanation look like: an injection from the B-set into the C-set that works only when $n\le 9$, and another injection from the C-set into the B-set that works only when $n\ge10$? –  Greg Martin Feb 1 '13 at 8:57

1 Answer 1

This is not a complete answer but I think its a step in the right direction

The $B(n)$ and $C(n)$ sets can be relate through code words. A $C(n)$ distribution can be described by a string of occupancy numbers. These are numbers that count how many balls are in each box. For example with $n=2$ you can have 2 balls in the first box, or 2 in the second, or 1 in each. The code words for these distributions are 20, 02, and 11. A $B(n)$ partition can be encoded using code words that indicate which elements are in the same subset of the partition. For example with $n=3$ and the set $S=(a,b,c)$ the code words are: 000, 001, 010, 011, 012, corresponding to the partitions: $(a,b,c)$, $(a,b)(c)$, $(a,c)(b)$, $(a)(b,c)$, $(a)(b)(c)$.

You can map a $C(n)$ code word to a $B(n)$ code word by replacing the first number in the $C(n)$ word, and all its occurences, with 0, then take the next of the original numbers and replace it and all its occurences with 1 and so on until all the numbers have been replaced. The result will be a $B(n)$ code word. Doing this for $n=3$ gives the following $C(n)\mapsto B(n)$ mappings: $111\mapsto 000$, $003\mapsto 001$, $030\mapsto 010$, $300\mapsto 011$, $210\mapsto 012$, $120\mapsto 012$, $201\mapsto 012$, $021\mapsto 012$, $102\mapsto 012$, $012\mapsto 012$.

There are 10 $C(3)$ code words with 4 of them mapping onto 4 unique $B(3)$ code words and 6 of them mapping onto the same $B(3)$ code word. All 5 of the $B(3)$ code words are accounted for by one or more of the 10 $C(3)$ code words. With $n=4$ there are 5 $B(4)$ words with unique $C(4)$ words, 3 of them with 2 $C(4)$ words each, and 6 of them with 4 $C(4)$ words each. The $C(4)$ code words account for 14 of the 15 $B(4)$ code words. The one unaccounted $B(4)$ code word is 0123 which would require a $C(4)$ code word with 4 unique occupancy numbers which is impossible. The four smallest unique occupancy numbers are 0 1 2 3 and they sum to 6.

One way to answer the question then is to explain how the above mapping works for all $n$. How many $C(n)$ code words map to a given $B(n)$ code word? How many $B(n)$ code words have no corresponding $C(n)$ code word and why?

share|improve this answer

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.