Combinatorics: Number of ways to distribute 12 balls in group, with given conditions

Question

The number of ways in which 12 identical balls can be grouped in four marked non empty sets A,B,C,D such that n(A) < n(B) is ?

The answer given is 70.

This is how I solved it:-

Now to distribute 12 identical balls to 4 different group such that no group is empty, we have $a+b+c+d = 12$, $$^{12-1}C_{4-1}$$ ways but we cannot have $a=b$ (as $a$ and $b$ are variables and interchangeable n(A) < n(b) and n(A) > n(b) mean the same), which also means that all $a, b, c,d$ should not be equal (as $a,b,c,d$ are variables and interchangeable) i.e. we need to exclude cases of $a=b=c=d$, but there is only one case that is possible which is $a=b=c=d=3$, thus total ways $=$ $$^{12-1}C_{4-1}-1$$ but that equals 164 but answer given is 70. What am I doing wrong? How will you solve the question?

Answer 1

Since the sets are non-empty, we can consider the number of nonnegative integer solutions to

$$a+b+c+d = \color{blue}{8}$$

• Consider first the distributions with $a=b=k$ with $k=0, \ldots , 4$. For a given $k=0,\ldots ,4$ the number of non-negative integer solutions to $c+d = 8-2k$: $\color{blue}{8-2k+1}$
• $\Rightarrow$ number of distributions with $a=b$: $\color{blue}{\sum_{k=0}^{4}(8-2k+1)=25}$
• number of all possible distributions without further restriction: $\color{blue}{\binom{8+3}{3}=165}$

Now, because of symmetry there are equally many distributions with $a<b$ and with $a>b$. Hence, the number of distributions with $a<b$ is

$$\color{blue}{\frac 12 \left(165 - 25\right)=70}$$

Answer 2

A different approach could be:

$(x^1+x^2+x^3+x^4+...+x^{11}+x^{12})^2 [x^2(x)+x^3(x+x^2)+...]$

And then find the coefficient of $x^{12}$ in the above expression

Answer 3

Answer will be $$\dfrac{^{12-1}C_{4-1} - K}{2}$$

Here K are the cases when $a =b$, which can be calculated using $2a + c + d =12$, which is

Coefficient of $x^{12}$ in $(x + x^2 + .... + x^{12})^2(x^2 + x^4 + ...... + x^{12})$

$\implies$ coefficient of $x^{12}$ in $(1 - x)^{-2} (x - x^{13})^2 (x^2 - x^{14}) (1 - x^2)^{-1}$

$\implies$ coefficient of $x^{8}$ in $(1 - x)^{-2} (1 + x^2 + x^4 + ..... + x^{12})$.

Now you can calculate easily.

Answer 4

Consider $b=a+x_1$ where $x_1\ge1$

Eqn becomesm $2a+x_1+c+d=12$ and $,a, x_1, c, d\ge1$. So we need to find number of positive integral solutions of the eqn

for a=1 we get $x_1+c+d=10$ Number of solutions=C(9,2)=36

for a=2 we get $x_1+c+d=8$ Number of solutions=C(7,2)=21

for a=3 we get $x_1+c+d=6$ Number of solutions=C(5,2)=10

for a=4 we get $x_1+c+d=4$ Number of solutions=C(3,2)=3

for a=5 we get $x_1+c+d=2$ Number of solutions=0

Total number os solutions=70

Answer 5

We have that, concerning the number of solutions, we can re-state the problem as $$ \eqalign{ & \left\{ \matrix{ 1 \le a,b,c,d \hfill \cr a < b \hfill \cr a + b + c + d = 12 \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le x_{\,1} ,x_{\,2} ,x_{\,3} ,x_{\,4} \hfill \cr x_{\,1} < x_{\,2} \hfill \cr x_{\,1} + x_{\,2} + x_{\,3} + x_{\,4} = 8 \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad \left\{ \matrix{ 0 \le x_{\,1} ,y_{\,2} ,x_{\,3} ,x_{\,4} \hfill \cr x_{\,2} = x_{\,1} + y_{\,2} + 1 \hfill \cr 2x_{\,1} + y_{\,2} + x_{\,3} + x_{\,4} = 7 \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le x_{\,1} ,x_{\,2} ,x_{\,3} ,x_{\,4} \hfill \cr x_{\,2} + x_{\,3} + x_{\,4} = 7 - 2x_{\,1} \hfill \cr} \right. \cr} $$

Therefore the number of solutions will be the number of weak compositions of $7-2k \; | \,0 \le k \le 3$ into $3$ parts, i.e. $$ \eqalign{ & N = \sum\limits_{k = 0}^3 { \left( \matrix{ 7 - 2k + 3 - 1 \cr 7 - 2k \cr} \right)} = \sum\limits_{k = 0}^3 {\left( \matrix{ 9 - 2k \cr 2 \cr} \right)} = \cr & = \left( \matrix{ 9 \cr 2 \cr} \right) + \left( \matrix{ 7 \cr 2 \cr} \right) + \left( \matrix{ 5 \cr 2 \cr} \right) + \left( \matrix{ 3 \cr 2 \cr} \right) = {{9 \cdot 8 + 7 \cdot 6 + 5 \cdot 4 + 3 \cdot 2} \over 2} = \cr & = 70 \cr} $$