Suppose that there are $m$ boxes which hold balls.

  • Two boxes hold exactly 3 balls each. These two boxes are placed at each end of the line.
  • The remaining $m-2$ boxes hold exactly 2 balls each.

There are also exactly $2m+2$ coloured balls. There are 5 different colours. Suppose they are black(B), white(W), yellow(Y), green(G), red(R). The number of black balls is $n_B$, the number of white balls is $n_W$ and so on.

Note: There can be zero balls of a particular colour. So there might in fact only be three colours, for example.

The order of the boxes (imagine the boxes are placed in a line) do matter, but symmetry is allowed. i.e. if you read it from left to right and right to left, then it is considered the same thing. For example, $(BBW,BW,WW,BB,WWW)$ is equivalent to $(WWW,BB,WW,BW,WBW)$.

The actual content of the boxes has no order. For example if a box has two red balls and one blue ball (RRB), then that is the same as having one blue ball and two red balls (BRR).

Determine the number of ways you can put the balls into the box.

I have read some similar problems on Stack Exchange and other websites, but this question seems to be more generalised, meaning such techniques wouldn't work for this question.

  • $\begingroup$ It seems to me that the fact that there are $2m+2$ coloured balls is an irrelevant information almost? Or am I missing something? Also do you have to put ALL the balls in the box? $\endgroup$
    – Jack Yoon
    Apr 28 '15 at 11:48
  • $\begingroup$ Two of the boxes hold exactly 3 balls each (so 6 balls all together). The remaining $m-2$ moxes hold 2 balls each (so $2(m-2)$ balls all together). In total, there are $2(m-2)+6 = 2m+2$ balls. Since each box either holds EXACTLY 2 or 3 balls (no less, no more), all of the $2m+2$ balls must be put in one of the boxes. $\endgroup$
    – James S
    Apr 28 '15 at 12:00
  • $\begingroup$ Yes, but now that you've pointed out without example that I forgot the condition "The two boxes holding 3 balls are placed at each end of the line." which I have now added in the question. But yes, you are right. $\endgroup$
    – James S
    Apr 28 '15 at 12:10
  • $\begingroup$ And I deleted my comment since you clarified the question to show that those arrangements were not allowed. But can you have fewer than three colors? $\endgroup$
    – David K
    Apr 28 '15 at 12:12
  • $\begingroup$ You can even have just one colour. But if all the balls are red, then there is just one way to put all identical red balls in the boxes. I just put in the "three colours" as an example to demonstrate you don't necessarily need to have five colours. Rather, five is just the upperbound for the number of colours you have. $\endgroup$
    – James S
    Apr 28 '15 at 12:20

Let us consider a box that can contain $n$ balls. There can be $0$, $1$,... or $n$ balls of a given color. Let us formally write $$\alpha_n(z)=1+z+\cdots+z^n.$$ And consider now a product like $\prod_c\alpha_n(z_c)$ where $c=B,\,W,\,R,\,G,\,Y$. It is a sum of terms $\prod_c z_c^{q_c}$. Each valid configuration corresponds to such a term where $\sum_cq_c=n$. Take the example with $n=2$ and three colors $A,B$ and $C$. $\alpha_2(z)=1+z+z^2$ and $\prod_c\alpha_2(z_c)=\alpha_2(z_A)\alpha_2(z_B)\alpha_2(z_C)=(1+z_A+z_A^2)(1+z_B+z_B^2)(1+z_C+z_C^2)$, $$\prod_c\alpha_2(z_c)=1+\color{red}{z_A+z_B+z_C}+\color{blue}{z_A^2+z_Az_B+z_Az_C+z_B^2+z_Bz_C+z_C^2}+\text{higher order terms}$$ The $1$ corresponds to the empty box, the terms in red to the configuration with one ball in the bax (either $A$, $B$ or $C$), the blue terms correspond to configurations with exactly two balls in the box. There are six such configurations. The other terms correspond to configurations with more than two balls in the box, but not more than twice the same color.

Therefore, the number of configurations for the box, if there are $k$ colors, is $C^k_n=[z^n]\alpha_n(z)^k$. (Where $[z^n]f(z)$ means the coefficient of $z^n$ in $f(z)$.)

So to answer the question, we can write the answer as $$\left[\prod_cz_c^{n_c}\right]\prod_c\alpha_3(z_c)^2\alpha_2(z_c)^{m-2}= \prod_c\left(\left[z^{n_c}\right]\alpha_3(z)^2\alpha_2(z)^{m-2}\right)=\prod_cD(n_c).$$ We can expand $\alpha_2(z)^{m-2}$ using the multinomial expansion and we get $$\alpha_3(z)^2\alpha_2(z)^{m-2}=\left(1+2z+3z^2+4z^3+3z^4+2z^5+z^6\right)\sum_{p,q}\frac{(m-2)!}{p!q!(m-2-p-q)!} z^{p+2q}$$ where the sum runs over all possibilities leading to positive arguments in the factorials. For instance if $n_B=4$ we find $$\begin{split}D(4)&=[z^4]\alpha_3(z)^2\alpha_2(z)^{m-2}\\& =3+4(m-2)+3(m-2)+3\frac{(m-2)(m-3)}2+2\frac{(m-2)(m-3)(m-4)}6+\frac{(m-2)(m-3)(m-4)(m-5)}{24}.\end{split}$$ It seems that the answer is quite difficult to express in a more readable or general way. But if someone has a better idea, I would enjoy reading it.

Note: One can count the total number of admissible configurations $$ [z^{2m+2}]\alpha_3(z)^{10}\alpha_2(z)^{5m-10}.$$ It is equal to $$[z^{2m+2}] \sum_{j,k,p,q,r}\frac{10!\;(5m-10)!}{j!k!p!q!r!(10-j-k)!(5m-10-p-q-r)!}z^{j+2k+p+2q+3r}.$$

(Added in edit) This last expression can be written in a more usal way as $$\sum_{\substack{j,k,p,q,r\geq0\\j+k\leq10\\p+q+r\leq5m-10\\j+2k+p+2q+3r=2m+2}}\frac{10!\;(5m-10)!}{j!k!p!q!r!(10-j-k)!(5m-10-p-q-r)!}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.