0
$\begingroup$

I have 40 balls:
10 x Red
10 x Blue
10 x Green
10 x Yellow

How can I count combinations of 20 balls?

I checked answer and it is 891 but how I calculate it?

Thanks!

$\endgroup$
1
  • $\begingroup$ you want the coefficient of $x^{20}$ in $(1+x+\dots+x^{10})^4$ $\endgroup$
    – Asinomás
    Jun 1 '17 at 20:53
3
$\begingroup$

You need to use generating function in order to solve this. Since there are $10$ balls of each type, you note that for every color you get: $(1+x+x^2+x^3+...+x^{10})$. Since there are four colors you get: $(1+x+x^2+x^3+...+x^{10})^4$.

Now - you are looking for a way to count the number of combinations of 20 balls. This is the same question as asking what is the coefficient of $x^{20}$.

Note that $(1+x+x^2+x^3+...+x^{10})^4 = (\frac{1-x^{11}}{1-x})^4$.

Now, we get $(1-x^{11})^4 \frac{1}{(1-x)^4}$ which by calculating and opening the first product we will get that the coefficient of $x^{20}$ is $\binom{23}{3}-4\binom{12}{3} = 891 $ as needed.

$\endgroup$
1
$\begingroup$

You seek the number of whole number four-tuples whose elements sum to 20 and in which no element is greater than 10

Stars and Bars tells you that the number whole number $n$-tuples summing to $p$ is $\binom{n+p-1}{n-1}$

To subtract off all the cases in which one colour appears more than 10 times you can take advantage of the fact that only 1 of the four colours can ever appear more than 10 times.

so for each of the four colours we need to subtract all the ways that the remaining three colours can sum to anything less than 10.

in the end we have ...

$$N_{tot} = \binom {23}{3} -4 \sum_{p=0}^9 \binom{p+2}{2}=891$$

$\endgroup$

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.