Generating functions combinatorical problem

277 Views Asked by At

In how many ways can you choose $10$ balls, of a pile of balls containing $10$ identical blue balls, $5$ identical green balls and $5$ identical red balls?

My solution (not sure if correct, would like to have input):

Define generated function:

$$\begin{align} A(x) & =(x^0+x^1+x^2+...+x^{10})(x^0+x^1+x^2+...+x^5)(x^0+x^1+x^2+...+x^5) \\ & ={1-x^{11} \over 1-x}\cdot \left({1-x^6 \over 1-x}\right)^2 \\ & =(1-x^{11})(1-2x^6+x^{12}) \cdot {1 \over (1-x)^3} \\ & =(1-2x^6-x^{11}+x^{12}+2x^{17}-x^{23})\cdot \sum_{n=0}^∞ {n+2 \choose 2} \cdot x^n. \end{align}$$

We look for the coefficient of $x^{10}$, so we get:

$$a_{10}=1 \cdot {10+2 \choose 2}-2\cdot {4+2 \choose 2}=36.$$

This seems incorrect (sadly I'm terrible in 'ordinary combinatorics' so I'm not sure how to calculate this 'regularly'). I would love to get input and hints.

Thanks in advance.

1

There are 1 best solutions below

2
On BEST ANSWER

Here’s one elementary approach. As you see, it confirms your result.

Let $b,g$, and $r$ be the numbers of blue, green, and red balls chosen to make up a set of $10$ balls. You’re looking for the number of solutions in non-negative integers to the equation $$b+g+r=10\;,\tag{1}$$ subject to the condition that $g\le 5$ and $r\le 5$. (You also have to have $b\le 10$, but that imposes no additional constraint when the sum is to be $10$.) Without the upper bounds this is a standard stars-and-bars problem whose solution is

$$\binom{10+3-1}{3-1}=\binom{12}2\;.$$

However, this count includes solutions with too many green or red balls. Let $g'=g-6$; then there is a bijection between solutions to $$b+g'+r=4\tag{2}$$ in non-negative integers and solutions to $(1)$ for which $g>5$. Thus, we need only count solutions to $(2)$ to get the number of solutions to $(1)$ with $g>5$. This is another stars-and-bars problem, and the answer is

$$\binom{4+3-1}{3-1}=\binom62\;.$$

Similarly, there are $\dbinom62$ solutions to $(1)$ that have $r>5$. There are no solutions that exceed the upper limits on both $g$ and $r$, so the number of solutions to $(1)$ that satisfy all of the conditions is

$$\binom{12}2-2\binom62=36\;.$$