1
$\begingroup$

I'm interested in knowing and understanding the solution to the following problem:

given $26$ balls - $8$ yellow, $7$ red and $11$ white - how many ways are there to select $12$ of them (all balls of the same colour are indistinguishable). I've read something about generating functions but I hoped there was a more straightforward way to "see" the solution...I really can't figure it out. Thanks in advance for your help!

$\endgroup$
  • 1
    $\begingroup$ What about $\binom{26}{12}$? $\endgroup$ – HeMan Jun 18 '15 at 18:50
  • $\begingroup$ This is the number of sets of size 12 that can be made of a set of 26 elements. $\endgroup$ – HeMan Jun 18 '15 at 18:51
  • 1
    $\begingroup$ But she's just asking how many ways are there to select 12 of them. $\endgroup$ – HeMan Jun 18 '15 at 18:52
  • 1
    $\begingroup$ I'm sorry, I should have said: balls of the same colour are indistinguishable! $\endgroup$ – lucia de finetti Jun 18 '15 at 18:56
  • $\begingroup$ @Peter The fact is I don't really know how to use that...I thought of that but I don't think I know how to work with it! $\endgroup$ – lucia de finetti Jun 18 '15 at 18:59
3
$\begingroup$

Forget for a while about the fact that the numbers of each colour are limited. If there were at least $12$ of each colour, the problem would be straightforward Stars and Bars. The answer would be $\binom{12+3-1}{3-1}$.

From this we must subtract the "bad" choices that involve using more balls of a given colour than are available. The bad choices are (i) too many yellow, (ii) too many red, and (iii) too many white. Note that we can count these separately and add, since we will never need simultaneously too many balls of two or more colours.

We count the number of choices with too many yellow, that is, $9$ or more. The number of ways to have $9$ yellow or more is the number of ways to choose $3$ balls from yellow, red, and/or white to accompany $9$ yellow. This is easy Stars and Bars, but also can be done by explicit listing.

The number of choices with too many red is done the same way. The number of choices with too many white needs no machinery.

$\endgroup$
2
$\begingroup$

Let $y,r,w$ denote the number of yellow balls, red balls and so on... Then you need to find the number of solutions to the following equation $$y+r+w=12 \qquad \text{ with } 0 \leq y \leq 8, 0 \leq r \leq 7, 0 \leq w \leq 11.$$

Can you proceed from here?

$\endgroup$
  • $\begingroup$ I thought about this formalism but no, I don't know how to proceed in that way... $\endgroup$ – lucia de finetti Jun 18 '15 at 18:57
  • $\begingroup$ Someone care to help? Could it be a stars and bars problem? Still, I'm not sure how... $\endgroup$ – lucia de finetti Jun 18 '15 at 19:03
  • $\begingroup$ @luciadefinetti since you want to avoid Generating functions (which in my opinion is the easiest way to handle this) you need to come up with some (ugly) version of exclusion-inclusion principle. For details you may want to check this math.stackexchange.com/questions/553960/… $\endgroup$ – Anurag A Jun 18 '15 at 19:09
  • $\begingroup$ Thank you! So to proceed from your sugestion I should use Generating Functions? $\endgroup$ – lucia de finetti Jun 18 '15 at 19:11
  • $\begingroup$ @luciadefinetti yes I would recommend that. In fact the answer given by "Kesarwany" will work. $\endgroup$ – Anurag A Jun 18 '15 at 19:13
2
$\begingroup$

Multiply $\displaystyle(1+x +...+x^8)(1+x+..+x^7)(1+x+..+x^{11})$, and the coefficient of $x^{12}$ of this product is your answer.

$\endgroup$
  • $\begingroup$ Thank you, I get the sense of it but I don't know much about generating functions and I hoped there was a different way to solve the problem! $\endgroup$ – lucia de finetti Jun 18 '15 at 19:04
  • $\begingroup$ I think answer will be 65 $\endgroup$ – user226263 Jun 18 '15 at 19:11
0
$\begingroup$

User226263 explanation using generating functions makes it straightforward. If you don't know much about generating functions then that explanation just nails it. In the product:

$$P(x) = \left(1+x +\cdots+x^8\right) \left(1+x+\cdots +x^7\right) \left(1+x+\cdots +x^{11}\right)$$

the coefficient of $x^{12}$ is the number of ways you can pick a term $x^a$ from the first bracket, $x^b$ from the second bracket and $x^c$ from the third bracket such that $a+b+c = 12$. This then corresponds to precisely to picking $a$ yellow balls, $b$ red balls and $c$ white balls such that you're picking 12 balls in total.

The general function method then leads to a simplification because you are now free to use algebra, calculus or whatever other methods to extract the desired coefficients, using formal methods one is then less prone to make errors. In this case, we can write:

$$P(x) = \frac{\left(1-x^9\right)\left(1-x^8\right)\left(1-x^{12}\right)}{\left(1-x\right)^3}$$

We can then use that:

$$\frac{1}{\left(1-x\right)^3} = \sum_{n=0}^{\infty}\binom{n+2}{2}x^n$$

Therefore the coefficient of $x^{12}$ is given by:

$$\binom{14}{2} - \binom{5}{2} - \binom{6}{2} -1 = 65$$

$\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.