Why are these two ways of counting the same combinatorial object not yielding the same result?

52 Views Asked by At

In how many ways can we distribute 20 black balls and 2 white balls (indistinguishable modulo color) in 5 numbered glasses such that the fifth one doesn't have more black balls than white balls?

My strategy was to break this problem into 6 incompatible scenarios according to how many balls we decide to put in the fifth glass: (i) no balls, (ii) 1W, (iii) 1W1B, (iv) 2W, (v) 2W1B, (vi) 2W2B.

Therefore, the are

$${23\choose20}{5\choose2} + {23\choose20}{4\choose1} + {22\choose19}{4\choose1} + {23\choose20} + {22\choose19} + {21\choose18} = 15 {23\choose20} + 5{22\choose19} + {21\choose18}$$

total distributions.

However, I was told each of these scenarios is equivalent to counting anagrams of $m,n,k$ copies of B, W, G respectively. But when we count anagrams of BBBBBBBBBBBBBBBBBBBBBBBBBWWGGG isn't the answer $\frac{25!}{20!2!3!}$? That's not the same as ${23\choose20}{5\choose2}$.

I'm seriously confused.

2

There are 2 best solutions below

3
On BEST ANSWER

The partition into the six possible distinguished cases is correct.

We have that the number of ways to put $b$ black balls into $g$ labelled (numbered) glasses is equivalent to the number of weak compositions of $b$ into $g$ parts, which is $$ \binom{b+g-1}{b} $$

Similarly for the white balls.

Therefore $$ \eqalign{ & N = \sum\limits_{cases} {\left( \matrix{ b + g - 1 \cr b \cr} \right)\left( \matrix{ w + g - 1 \cr w \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\,j\, \le \,2} {\left( \matrix{ 20 - k + 3 \cr 20 - k \cr} \right)\left( \matrix{ 2 - j + 3 \cr 2 - j \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,\,j\, \le \,2} {\left( \matrix{ 23 - k \cr 20 - k \cr} \right)\left( \matrix{ 5 - j \cr 2 - j \cr} \right)} = \cr & = \sum\limits_{0\, \le \,j\,,\,\,k\, \le \,2} {\left( \matrix{ 23 - k \cr 20 - k \cr} \right)\left( \matrix{ j - k \hfill \cr j - k \hfill \cr} \right)\left( \matrix{ 5 - j \cr 2 - j \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,2} {\left( \matrix{ 23 - k \cr 20 - k \cr} \right)\left( \matrix{ 6 - k \cr 2 - k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,2} {\left( \matrix{ 23 - k \cr 3 \cr} \right)\left( \matrix{ 6 - k \cr 4 \cr} \right)} = \cr & = \left( \matrix{ 23 \cr 3 \cr} \right)\left( \matrix{ 6 \cr 4 \cr} \right) + \left( \matrix{ 22 \cr 3 \cr} \right)\left( \matrix{ 5 \cr 4 \cr} \right) + \left( \matrix{ 21 \cr 3 \cr} \right) = \cr & = 15\left( \matrix{ 23 \cr 3 \cr} \right) + 5\left( \matrix{ 22 \cr 3 \cr} \right) + \left( \matrix{ 21 \cr 3 \cr} \right) = \cr & = 15\left( \matrix{ 23 \cr 20 \cr} \right) + 5\left( \matrix{ 22 \cr 19 \cr} \right) + \left( \matrix{ 21 \cr 18 \cr} \right) = \cr & = 35595 \cr} $$ which fits with your computation.

Concerning the Anagrams analogy, it is correct that the case in which, e.g., the 5th glass is empty corresponds to the anagrams of $$[20 \times B, 5 \times W, 3 \times G]$$ since the $G$ stands for the separation between two consecutive of the four glasses.
And that is in fact equal to the weak compositions of $20$ into four parts, times the compositions of $5$ into four parts.

Now, instead, the multinomial $$ N_{0,0} = \left( \matrix{ 28 \cr 20,5,3 \cr} \right) = {{28!} \over {20!5!3!}} $$ which appears in the expansion of the trinomial $$ \eqalign{ & \left( {B + W + G} \right)^{\,28} = \cr & = \ldots + B^{\,20} W^{\,5} G^{\,3} + B^{\,19} WBW^{\,4} G^{\,3} + \ldots + \ldots \cr & \cdots + GB^{\,12} W^{\,2} B^{\,6} GW^{\,2} B^{\,2} WG + \cdots \cr & = \ldots + \left( \matrix{ 28 \cr 20,5,3 \cr} \right)B^{\,20} W^{\,5} G^{\,3} + \ldots \cr} $$ is going to count also how a certain number of white and black balls inside a single glass alternate in color, that is the situation in which the glass has a one-ball diameter and we distinguish not only by the content in black/white of each glass but also by the color layering.

0
On

It's not the same as counting anagrams, because in anagrams the order of different letters matter, whereas there is no difference in what order you put white and black balls in the glass.

Consider a simpler problem: how many ways are there to put 1 white and 2 black balls in the glass. Of course it's only one! However, you have three anagrams of BBW: BBW, BWB, WBB.