1
$\begingroup$

With how many ways can we choose $9$ balls of a box that contains $12$ balls, of which $3$ are green, $3$ are white, $3$ are blue and $3$ are red?

$$$$

I have done the following:

$x_1=\# \text{ green balls that we choose }$

$x_2=\# \text{ white balls that we choose }$

$x_3=\# \text{ blue balls that we choose }$

$x_4=\# \text{ red balls that we choose }$

$$x_1+x_2+x_3+x_4=9, \ \ \ \ 0 \leq x_i \leq 3$$

$$\\$$

The number of solutions of the equation: $x_1+x_2+x_3+x_4=9, \ \ \ x_i \geq 0 \ \ \ $ is

$$\binom{9+4-1}{3}=\binom{12}{3}$$

Then I take the cases I don't want, to subtract them from the number above.

$x_1>3 \Rightarrow x_1 \geq 4$

$y_1=x_1-4 \geq 0$

So we become the equation:

$$y_1+4+y_2+y_3+y_4=9, \ \ \ y_i \geq 0 \ \ \ \ \Rightarrow y_1+y_2+y_3+y_4=5, \ \ \ y_i \geq 0$$

And the number of solutions are: $$\binom{4+5-1}{3}=\binom{8}{3}$$

We do the same for $i=2,3,4$.

$$\\$$

Finally the solution is: $$\binom{12}{3}- 4\cdot \binom{8}{3}=-4$$

That cannot be right..

What have I done wrong??

$\endgroup$
  • 1
    $\begingroup$ Why it is not simply $\binom{12}{9}$? $\endgroup$ – Jika Jun 2 '14 at 20:24
  • 1
    $\begingroup$ why $x_{1}$ is greater than 3 in middle of question ? $\endgroup$ – Karo Jun 2 '14 at 20:24
  • 1
    $\begingroup$ It looks like you are overcounting. You cannot just multiply by four, because there are solutions where $x_{1} \geq 4$ and, say, $x_{2} \geq 4$, which you are double counting. $\endgroup$ – Alex Wertheim Jun 2 '14 at 20:29
  • 1
    $\begingroup$ we have another condition that $x_{i} < 4$ because we have just 3 balls of each color so you effect this condition you should use generation function. just use choosing and divide and conquer. $\endgroup$ – Karo Jun 2 '14 at 20:33
  • 4
    $\begingroup$ It's easier to choose 3 balls not to take, since then you don't have to worry about running out of any color. $\endgroup$ – user2357112 Jun 2 '14 at 20:34
4
$\begingroup$

Generating function solution: Each color is represented by: $$ 1 + z + z^2 + z^3 = \frac{1 - z^4}{1 - z} $$ All four colors are then: $$ \left( \frac{1 - z^4}{1 - z} \right)^4 $$ and you want 9 balls, i.e., the coefficient of $z^9$, ellipses are terms that don't affect the result: \begin{align} [z^9] \left( \frac{1 - z^4}{1 - z} \right)^4 &= [z^9] \frac{(1 - z^4)^4}{(1 - z)^4} \\ &= [z^9] (1 - 4 z^4 + 6 z^8 - \ldots) (1 - z)^{-4} \\ &= [z^9] (1 - z)^{-4} - 4 [z^5] (1 - z)^{-4} + 6 [z] (1 - z)^{-4} \\ &= (-1)^9 \binom{-4}{9} - 4 \cdot (-1)^5 \binom{-4}{5} + 6 \cdot (-1)^1 \binom{-4}{1} \end{align} Use of the generalized binomial theorem finishes this off: $$ \binom{-m}{k} = (-1)^k \binom{k + m - 1}{m - 1} $$ for $m \in \mathbb{N}$. You get 20 as result.

$\endgroup$
4
$\begingroup$

The approach of user3294068 is, for these numbers, an efficient way to attack the problem.

Let us marry that with the Stars and Bars approach of the OP. Let $w_1$ be the number of greens that we don't choose, $w_2$ the number of whites that we don't choose, and so on. We want to find the number of solutions of $w_1+w_2+w_3+w_4=3$ in non-negative integers.

The number of solutions is $\binom{3+4-1}{4-1}$, which is $20$.

$\endgroup$
3
$\begingroup$

Assuming we do not care about the order in which the balls are selected, the number of ways of choosing $9$ balls from the box is the same as the number of ways of leaving $3$ balls in the box, which is much easier to calculate.

If we number the balls $1$ to $12$, then there are $12\choose 3$ ways of doing this. But removing balls $1,4,7$ would be the same as removing $2,4,7$, since balls $1$ and $2$ are both red. So we need to break it down to:

  • Number of ways to leave one ball of each of $3$ colors = ${4 \choose 3} = 4$.
  • Number of ways to leave two balls of one color and one ball of another color $ = 4\cdot 3 = 12$.
  • Number of ways to leave three balls of one color = $4$.

Total number $= 4 + 12 + 4 = 20$ ways of removing $9$ balls.

$\endgroup$
1
$\begingroup$

Nobody seems to have actually answered the question: What went wrong? Why is the (attempted) answer negative? We can certainly see the answer is 20 and not -4, but how did the method giving the latter answer go wrong?

Andre and user329.. have both presented a nice, neat way of breaking down the problem in elementary methods. Vonbrand has adeptly applied the more powerful method of generating functions, although I am going to guess that this might be a bit too advanced for the intended audience.

The problem is one of double-counting, and the answer is to use the method of inclusion-exclusion.

What you have said is:

There are $\binom{12}{9}=220$ ways of getting $(x_1,x_2,x_3,x_4)$ and I want to exclude the ones where something "bad" happens. Here "bad" means $x_1\ge 4$, $x_2\ge 4$, $x_3\ge 4$, or $x_4\ge 4$. That's four different bad criteria, and you are correct when you say:

The number of ways we could get $x_1\ge 4$ is just like solving $x_1'+4+x_2+x_3+x_4=9$, i.e. $x_1'+x_2+x_3+x_4=5$, which is $\binom{8}{3}=56$.

So you have the following so far:

All possible events: 220
Bad outcome #1: 56
Bad outcome #2: 56
Bad outcome #3: 56
Bad outcome #4: 56

However, it is not true (or even possible) that the total number of bad outcomes is $4\times 56$. (Having seen the other answers, we know it should be 200 to leave 20 remaining.) So there must be some sort of over-count going on here.

The reason subtracting $4\times56$ is too much is because when you count bad outcome #1 and get 56, some of those also include bad outcome #2.

Because you are choosing 9 balls, you could possible have an illegal answer where $x_1\ge 4$ and also $x_2\ge 4$. There is some overlap among each of these 56s.

To count that effectively, you go back to the idea you had before and modify it:

$$x_1+x_2+x_3+x_4 = x_1'+4+x_2'+4+x_3+x_4=9$$

This gives you:

$$x_1'+x_2'+x_3+x_4=1$$

and there are only four ways to do this. So what you have now is:

All possible events: 220
Bad outcome #1: 56
Bad outcome #2: 56
Bad outcome #3: 56
Bad outcome #4: 56
Bad outcome #1 and #2: 4
Bad outcome #1 and #3: 4
Bad outcome #1 and #4: 4
Bad outcome #2 and #3: 4
Bad outcome #2 and #4: 4
Bad outcome #3 and #4: 4

(If it were possible to have three bad outcomes at once, you'd have to keep going.)

So you start with 220, which includes the cases you want to count plus lots of bad cases. You can subtract out all of the ways one bad event happens:

$$220 - 4\times 56 = -4$,$

But the outcomes where two bad events are subtracted twice (we've included that type of outcome in two of our 56s). So you want to add those back in to balance things out:

$$220 - 4\times 56 + 6\times 4 = 20.$$

The idea you had was to exclude bad events, and you got started right, but to get the correct answer, you have to deal with this double-counting. The way to do that is called "inclusion exclusion" and it works fairly well for this type of problem if you apply it carefully.

It may help to see this visually and break down the quantities a little bit:

220 total

56 of each bad type

4 bad in each 2-type overlap

no overlap of 3+ types

we know where the 4s go

so that leaves 44 in each circle

Notice in that image that one overlapping region is not pictured.

total this leaves 20 left over

$\endgroup$
0
$\begingroup$
  1. If you choose balls of only $1$ color, there are $0$ ways.

  2. If you choose balls of $2$ colors, there are $0$ ways.

  3. If you choose balls of $3$ colors, there are ${4\choose3}=4$ ways.

  4. If you choose balls of $4$ colors, then you first pickup $1$ ball of each color in $1$ way. Now you need to choose $5$ balls from $2$ of each color. Now we can apply the same algorithm(1-4) for the remaining $5$. We can't choose balls of only $1$ or $2$ colors. For choosing $3$ balls, we first pickup $1$ of each color in ${4\choose3}=4$ ways and then we have $3$ ways of choosing the remaining $2$. This gives us $4\cdot3 = 12$ ways. For the case of $4$ colors, we pickup 4 balls of each color in $1$ way and then we have $4$ ways of picking the last one.

This gives us a total of $4+12+4 = \boxed{20}$ ways.

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