0
$\begingroup$

I have a quiz tomorrow in an elementary combinatorics class, and I'm trying to understanding these generating function problems. For some reason, I can't see to figure out how to set these two up. Also, when the problem asks "find the number of ways" I just have to find the generating function and then what terms' coefficient I'm interested is - not the actual coefficient itself.

Problem 1: Find the number of ways to select 10 balls from a bin containing 10 balls each of 5 different colors.

Maybe I'm just stupid, but I was having trouble interpreting this question - what is meant by "10 balls each of 5 different colors" ? Wouldn't that mean I have 50 balls, not 10 in the bin, or does it mean that each of the 10 balls could be any of 5 different colors (and if this is the case, I have no idea where to start). I just don't get what it's asking … (maybe I should have posted this in an English forum).

Problem 2: Now, find the number of ways to selected 10 balls when there are 10 balls of one color, but only 8 balls of the other 4 colors.

Here, again, I am shaky on the interpretation. Are there 8 of each remaining color (i.e. 32 balls with 8 of each of the 4 colors) - or are there are 8 balls along the total of 4 colors - and how would you set that up

All the other problems on the practice sheet were really straightforward, so I feel like there isn't anything tricky here - but I don't see how to start.

$\endgroup$
  • 1
    $\begingroup$ Yes, first problem's bin has $10 \cdot 5 = 50$ balls, the second has $10 + 8 \cdot 4 = 42$ balls. $\endgroup$ – gt6989b Apr 2 '14 at 17:33
2
$\begingroup$

Let's use generating functions.

  1. 10 balls out of a bin having 10 each of 5 colors: Each color can appear up to 10 times, i.e., it's generating function is $1 + z + \cdots + z^{10} = (1 - z^{11}) / (1 - z)$. We want 10 balls in all out of the above. As there are 10 balls of each color, it is the same as having an infinite number of balls: \begin{align} [z^{10}] \left( \frac{1 - z^{11}}{1 - z} \right)^5 = [z^{10}] (1 - z)^{-5} = (-1)^{10} \binom{-5}{10} = \binom{10 + 5 - 1}{5 - 1} = 1001 \end{align}
  2. 10 balls out of 10 of one color, 8 of each of the others: As above, ellipsis indicates terms that can't affect the result: \begin{align} [z^{10}] \frac{1 - z^{11}}{1 - z} \left( \frac{1 - z^9}{1 - z} \right)^4 &= [z^{10}] \frac{(1 - z^9)^4}{(1 - z)^5} \\ &= [z^{10}] (1 - 4 z^9 + \cdots) (1 - z)^{-5} \\ &= [z^{10}](1 - z)^{-5} - 4 [z](1 - z)^{-5} \\ &= (-1)^{10} \binom{-5}{10} - 4 \cdot (-1) \binom{-5}{1} \\ &= 981 \end{align}
$\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.