Fourteen numbered balls (i.e., $1$, $2$, $3$, $\ldots$, $14$) are divided in three groups randomly. Find the probability that sum of the numbers on the balls, in each group, is odd.
There is this line from the solution for the above question in the back of my book:
The total number of cases for dividing $14$ balls into three non-empty groups is$${{3^{14} – \binom{3}{1} 2^{14} + \binom{3}{2}}\over{3!}}$$
This is unclear to me, and the book does not offer any explanation for why this is true, it is simply asserted as clear. Could anyone explain how the book came up with this result?
Update. I had gotten $3^{14}/3! – 2^{14}/2! + 1$, which is clearly wrong since it's not a natural number. But why is that wrong?
Best Answer
We have $3$ groups call them $A,B,C$.
Claim 1: There are $3^{14}$ ways to place the $14$ balls so that each ball is in one of the groups. Rationale: each ball has three choices into which group to belong. So there are $\underbrace{3\times 3\times...\times 3} = 3^{14}$ ways to do this.
Note two things though. 1) This does not prevent selecting a way in such that one or two groups never get any balls and are empty. And 2) This counts the choice of $A=\{1,2,3,4,5\}, B=\{6,7,8,9,10\}, C=\{11,12,13,14\}$ as being distinct and different for the choice of $A=\{6,7,8,9,10\}, B=\{1,2,3,4,5\}, C=\{11,12,13,14\}$ whereas those choice should be considered the same. (They are both "Balls $1$ through $5$ in one group, balls $6$ through $10$ in another, and the rest in the third group")
Claim 2: There are ${3\choose 1}2^{14} - {3\choose 2}$ to place the $14$ balls into three groups so that at least one of the groups is empty.
Rationale: Before I explain claim 2, I'll makes claim 3 and 4.
Claim 3: there are ${3\choose 2}1^{14} = {3\choose 2}$ ways to place $14$ balls into three groups so that $2$ of the groups are empty. Rationale: There are ${3\choose 2}$ ways to which two groups are left empty. After that is decided we must place all the balls in the one remaining group. There is only $1$ way to do this (or if we like, each ball has $1$ choice so there is $1^{14}$ choices.)
Claim 4: there ${3\choose 1}2^{14}$ strategies to leaving one group empty and placing $14$ balls in the two remaining groups. However in some cases two of these stategies will have the same result. Rationale: We first choose which of the three groups to leave empty. There are ${3\choose 1}$ way to do this. And each of the balls have $2$ choices of groups to be placed in. So there are ${3\choose 1}2^{14}$ ways to plan to do this. However if we choose to leave one group empty and then choose to put all $14$ balls in a second group so as a result the first and third group are left empty, that is the exact same result as first choosing to leave the third group empty and then choosing to put all $14$ balls in the second group. So in these strategies the cases were two of the three groups are left empty are "double counted".
Putting claims 3) and 4) together we get claim 5:
Claim 5: the actual ways to place $14$ balls into $3$ groups so that at least one group is empty is ${3\choose 2}2^{14} - {3\choose 2}$. Rationale: There are ${3\choose 2}2^{14}$ strategies but that results in the ${3\choose 2}$ ways where two groups are left empty being "double counted". So we must subtract the extra ${3\choose 2}$ we counted twice to get ${3\choose 2}2^{14} - {3\choose 2}$ as the actually number.
So now
Claim 6: There are $3^{14}-({3\choose 1}2^{14}-{3\choose 2})= 3^{14}-{3\choose 1}2^{14} + {3\choose 2}$ ways to place $14$ balls into three groups so that no group is empty. Rationale: There are $M = 3^{14}$ ways total to group the $14$ balls and $N = {3\choose 1}2^{14}-{3\choose 2}$ will result in at least one group being empty then there are $M - N$ ways to group the $14$ balls without any of the groups being empty.
But note: We still have the issue of one group of balls in one group, the second int a second group, and the rest being in the third being considered distinct and different depending on how we label the groups.
Now consider: For any intrinsic sorting of "such and such balls in one group" there are $3$ groups we can put those "such and such balls". And for "and then so and so balls is another group" there are $2$ groups we can put those "so and so balls". And for "and the rest in the third" there is only $1$ group that can be "the third". So we counted there are $3!$ way to place the grouping "such and such, so and so, and the rest".
So in counting all the ways to sort $14$ balls into $3$ groups where we distinguish which groups each grouping of balls goes into and for each grouping there are $3!$ distinct ways of selecting the groups the without distinguishing the groups there are $\frac {\text{Total numbers of way to group}}{3!}= \frac{3^{14}-{3\choose 2}2^{14} + {3\choose 2}}{3!}$ ways to group them into three groups.