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?
1
-
2$\begingroup$ 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$? $\endgroup$– Greg MartinFeb 1, 2013 at 8:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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?