There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that the number of red balls is even or the number of yellow balls is odd?

in this question, being even or odd affects to what. As a result, the numbers of balls with different colors are same. I did not get it.

  • $\begingroup$ What does this have to do with generating functions? $\endgroup$ Apr 16 '14 at 16:05

You are asking for generating functions.

First of all, the total number of balls available is irrelevant, as long as it is enough to fill all slots. For simplicity, take infinite number of balls.

  • Red balls even: $1 + z^2 + \ldots = \frac{1}{1 - z^2}$
  • Yellow balls odd: $z + z^3 + \ldots = \frac{z}{1 - z^2}$
  • Any number of green balls: $1 + z + z^2 + \ldots = \frac{1}{1 - z}$

Now you have to consider (red even) + (yellow odd) - (red even and yellow odd), as the last case was considered twice in the first two collections:

  • Red balls even, others arbitrary: $\frac{1}{1 - z^2} \cdot \frac{1}{(1 - z)^2}$
  • Yellow balls odd, others arbitrary: $\frac{z}{1 - z^2} \cdot \frac{1}{(1 - z)^2}$
  • Red even, yellow odd: $\frac{z}{(1 - z^2)^2} \cdot \frac{1}{1 - z}$

In summary, you are interested in: $$ [z^{2005}] \left( \frac{1}{(1 - z^2) (1 - z)^2} + \frac{z}{(1 - z^2) (1 - z)^2} - \frac{z}{(1 - z^2)^2 (1 - z)} \right) $$ You can get the result by expanding in partial fractions and handle the resulting terms: $$ - \frac{1}{16 (1 + z)} - \frac{1}{8 (1 + z)^2} - \frac{1}{16 (1 - z)} + \frac{4}{5 (1 - z)^3} $$ Geometric series or the generalized binomial theorem with negative integer exponent finishes this off: \begin{align} (1 + u)^{-m} &= \sum_{k \ge 0} \binom{-m}{k} u^k \\ &= \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k \end{align}


By stars-and-bars, there are $\binom{2007}{2}$ ways to select 2005 balls without the even and odd conditions.

Write each choice as $(2R+r, 2Y+y, G)$ where $r,y\in\{0,1\}$. Most of the possible combinations come in matched quadruples with the same $R$ and $Y$, and in each such quadruple 3 of the four possibilities meet the condition.

The only combinations that don't fit into a quadruple are those where $2R+2Y=2004$, in which case the $r=y=1$ combination doesn't exist. So these additional combinations come in triples, where two out of the three combinations meed the condition.

There are $1003$ such triples.

So the total number of combinations that meet the even-odd condition should be

$$ \frac34\left( \binom{2007}{2} - 3\cdot 1003 \right) + 2\cdot 1003 $$


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.