Find the number of ways to select 2n balls from n identical blue balls, n identical red balls and n identical white balls, where n $\in$ $\mathbb N$

Question

Q: Find the number of ways to select 2n balls from n identical blue balls, n identical red balls and n identical white balls, where n $\in$ $\mathbb N$.

My working:

$(x+x^2+x^3+...)^3$

$=x^3(1+x+x^2+...)^3$

$= x^3 \sum_{r=0}^\infty \begin{pmatrix} {r+3-1}\\{r}\end{pmatrix}x^r$

$= \sum_{r=0}^\infty \begin{pmatrix} {r+2}\\{r}\end{pmatrix}x^{3+r}$

Hence the number of ways is $\begin{pmatrix} {2n-1}\\{2n-3}\end{pmatrix}$=$\begin{pmatrix} {2n-1}\\{2}\end{pmatrix}$.

However, the actual answer is $\begin{pmatrix} {2n+2}\\{2}\end{pmatrix}$$-3$$\begin{pmatrix} {n+1}\\{2}\end{pmatrix}$. Did i go wrong somewhere in my proof? Or is it some conceptual understanding gone wrong? Thanks!

Answer 1

This is same as the number of solutions to $$x+y+z = 2n$$ where $0 \leq x, y, z \leq n$. Thus we need the coefficient of $t^{2n}$ in \begin{align*} (1+t+t^2+ \cdots +t^n)^3 &= \left(\frac{1-t^{(n+1)}}{1-t}\right)^3\\ &=(1-3t^{(n+1)}+3t^{2(n+1)}-t^{3(n+1)})\left(1+\binom{3}{1}t + \binom{4}{2}t^2+ \cdots +\binom{3+k}{k+1}t^{k+1} + \cdots \right) \end{align*} Thus the required coefficient is $$\binom{2n+2}{2n} - 3 \binom{n+1}{n-1} = \binom{2n+2}{2} - 3 \binom{n+1}{2} $$

Answer 2

I think it's easiest to count this directly, without any fancy tricks. We actually end up with a simpler formula: $$\binom{n+2}{2}$$ or, equivalently, $$\frac{(n+1)(n+2)}{2}$$ (which is equal to the longer formula in @Muralidharan's answer).

Here's how it works:

The number $r$ of red balls is in the range from $0$ to $n,$ and the number $b$ of blue balls is also in the range from $0$ to $n.$

Given values for $r$ and $b,$ there's at most one possible value for the number of white balls: $w = 2n-r-b.$ But this potential number of white balls also has to be in the range from $0$ to $n.$ If $2n-r-b$ is in the range from $0$ to $n,$ then $\langle r, b, 2n-r-b\rangle$ is a triple we have to count. If $2n-r-b$ is not in that range, then we should skip that triple and not count it.

Since each ordered pair $\langle r, b\rangle$ has at most one corresponding $w,$ this is the same as counting the number of ordered pairs $\langle r, b\rangle$ such that $0 \le r \le n, 0 \le b \le n,$ and $0 \le 2n-r-b \le n.$

So our count is as follows, using the notation $\#X$ for the cardinality of a set $X\!\!:$

\begin{align} &\#\lbrace \langle r, b\rangle \mid 0 \le r \le n \;\land\; 0 \le b \le n \;\land\; 0 \le 2n-r-b \le n\rbrace \\= &\#\lbrace \langle r, b\rangle \mid 0 \le r \le n \;\land\; 0 \le b \le n \;\land\; r + b \le 2n \;\land\; n \le r+b\rbrace \\= &\#\lbrace \langle r, b\rangle \mid 0 \le r \le n \;\land\; 0 \le b \le n \;\land\; n-r \le b \le 2n-r\rbrace \\= &\#\lbrace \langle r, b\rangle \mid 0 \le r \le n \;\land\; \max(0,n-r) \le b \le \min(n,2n-r)\rbrace. \end{align}

For any $r \le n,$ we have $\max(0,n-r)=n-r$ and $\min(n,2n-r)=n,$ so the count above equals \begin{align} &\#\lbrace \langle r, b\rangle \mid 0 \le r \le n \;\land\; n-r \le b \le n\rbrace. \end{align}

You can see that for each value of $r$ from $0$ to $n,$ we have $r+1$ possible values of $b$, namely $n-0, n-1, n-2, \dots, n-r.$

It follows that the total count equals

\begin{align} \sum_{r=0}^n (r+1) &= \sum_{k=1}^{n+1} k \\&= \frac{(n+1)(n+2)}{2}, \end{align}

and this equals $$\binom{n+2}{2}$$ if you want to phrase the answer as a binomial coefficient.

Answer 3

Since we are selecting $2n$ balls from a total of $3n$ balls,

we can count how many ways we can choose the $n$ balls we are leaving out.

This is the number of solutions in nonnegative integers to $a+b+c=n$,

which is given by $\color{blue}{\dbinom{n+2}{2}}$.

---

Alternate solution:

We want to find the number of solutions to $x_1+x_2+x_3=2n$ where $0\le x_i\le n$ for each $i$.

If S is the set of all solutions in nonnegative integers and if $A_i$ is the set of solutions with $x_i>n$,

we have $\big|\overline{A_1}\cap\overline{A_2}\cap\overline{A_3}\big|=\big|S\big|-\big|A_1\big|-\big|A_2\big|-\big|A_3\big|=\color{blue}{\dbinom{2n+2}{2}-3\dbinom{n+1}{2}}$