Let there be two persons P1, P2. Now let there be $6n$ balls so that $2n$ balls are red, blue and green respectively. In how many ways can P1 and P2 get $3n$ balls?

And how about $2pn$ balls in $p$ colours?

Thanks :)


Suppose that there are $2pn$ balls in $p$ colors, $2n$ balls of each color. For $k=1,\dots,p$ let $x_k$ be the number of balls of color $k$ received by $P_1$; then the question asks for the number of solutions to $$\sum_{k=1}^px_k=pn\tag{1}$$ in non-negative integers $x_1,\dots,x_p$, subject to the condition that $x_k\le 2n$ for $k=1,\dots,p$. It’s well-known that the number of solutions to $(1)$ in non-negative integers without any upper bound conditions is $$\binom{pn+p-1}{p-1}=\binom{pn+p-1}{pn}\;.\tag{2}$$ From this total we must subtract the solutions that exceed the $2n$ limit in some term. In general this is a somewhat messy inclusion-exclusion calculation of a kind discussed several times on this site; see, for instance, the answer to this question. For $p=3$, however, it’s not bad.

If $p=3$, $(1)$ becomes $$x_1+x_2+x_3=3n\;,\tag{3}$$ and at most one of the terms can exceed $2n$. There is an easy bijection between solutions to $(3)$ in non-negative integers with $x_1>2n$ and solutions to $y_1+y_2+y_3=3n-(2n+1)=n-1$ in non-negative integers, and there are $$\binom{(n-1)+3-1}{3-1}=\binom{n+1}2$$ of the latter. Similarly, there are $\binom{n+1}2$ solutions to $(3)$ with $x_2>2n$ and another $\binom{n+1}2$ with $x_3>2n$. Thus, the answer to the original question (with $p=3$) is

$$\begin{align*} \binom{3n+2}2-3\binom{n+1}2&=\frac12\Big((3n+2)(3n+1)-3n(n+1)\Big)\\\\ &=3n^2+3n+1\;. \end{align*}$$

  • $\begingroup$ Thank you, great solution with a very clear explanation :) I'd rep you if I'd know how to. $\endgroup$ – Weedle Jan 15 '13 at 23:33
  • $\begingroup$ @Weedle: You’re very welcome. You need $15$ rep to upvote, so you can’t do that; what you can do, if you like, is accept the answer by clicking on the check-mark next to it. There’s more information here. $\endgroup$ – Brian M. Scott Jan 15 '13 at 23:40

Let $f(p,k)$ be the number of ways, a person can get $k$ balls given p colors and 2n balls in each color. Then we have

$f(p,3n) = \sum_{i=0}^{2n} f(p-1,3n-i)$

since from the first color we can have $i=0, 1, \ldots$ or $2n$ balls and then there are $p-1$ colors and $3n-i$ balls left.

We also have

$f(2,k) = k+1,\ \mbox{if}\ 0 \le k \le 2n \quad \mbox{or} \quad (4n-k)+1,\ \mbox{if}\ 2n < k \le 4n$

From this $f(3,3n)$ can easily computed, which gives the asked number since only the balls of Person $P_1$ matter.

In the general case we have the recursion

$f(p,k) = \sum_{i=0}^{\min(k,2n)} f(p-1,k-i)$.

  • $\begingroup$ Thank you for your reply, I'd like to rep you but I don't know how :( $\endgroup$ – Weedle Jan 15 '13 at 23:32

The first answer is simply 6n choose 3n

  • 1
    $\begingroup$ This is true if all balls can be distinguished from each other. But the questions suggests that balls of the same color cannot be distinguished. $\endgroup$ – coproc Jan 15 '13 at 13:14
  • $\begingroup$ But the first part of the question does not mention color at all. It simply asks in how many ways can one choose 3n balls from 6n balls. Thus 6n choose 3n. $\endgroup$ – Jakob Jan 15 '13 at 15:59
  • $\begingroup$ @Arnold: It is not $\binom{6n}{3n}$. You’re ignoring the obvious context: Weedle clearly wants to know the number of distributions of $3n$ balls to each person that are distinguishable strictly on the basis of the numbers of balls of each color that $P_1$ and $P_2$ have. $\endgroup$ – Brian M. Scott Jan 15 '13 at 18:39
  • $\begingroup$ Coproc and Brian, you are right. $\endgroup$ – Weedle Jan 15 '13 at 23:31

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.