3
$\begingroup$

Suppose there are $4$ red apples, $5$ green apples, and $6$ yellow apples, $9$ of them will be put into a box. In how many different ways can apples be placed in the box if at least there is one apple of each color?

I've tried to solve this problem and got the result of $673596$ different possible compositions. Here's how I try to solve it.

One apple of each color must be in the box, therefore the new sample space is that containing $3$ red apples, $4$ green apples and $5$ yellow apples $(3R, 4G, 5Y)$, and because there are already $3$ apples in the box, I just need to pick the remaining $6$ apples.

The problem now reduced to how much partition of $12$ objects into $4$ part namely $R$ (for red apples), $G$ (for green apples), $Y$ (for yellow apples) and $N$ (for none of the three) are possible, which is.

$$\sum \binom{12}{R,G,Y,N}$$

for $R+G+Y = 6$, and $N = 6$.

My question is whether there is any some kind of generalization of this problem so that I could solve it easily without deliberately looking for every possible arrangement of $R$, $G$ and $Y$ (which is how I try to solve the problem).

$\endgroup$
3
  • $\begingroup$ There's at least 2 selections unaccounted for ... $\endgroup$
    – user645636
    Feb 1, 2020 at 11:03
  • 1
    $\begingroup$ The way I read this question is that we only care about how many apples of each color are placed in the box, in which case your answer is far too large. Are you counting the number of ways the apples can be arranged within the box? $\endgroup$ Feb 1, 2020 at 11:39
  • $\begingroup$ We don't care about the arrangement of apples of the same color in the box, but we do care about compositions of each apple, such that ($4$R, $4$G, $1$Y) is different from ($1$R, $2$G, $6$Y). I think that assuming all object are different (even if it has same color) won't change the number of possibilities, or would it? $\endgroup$ Feb 1, 2020 at 11:58

3 Answers 3

3
$\begingroup$

I don’t understand your approach, and it gives the wrong result, so it must be wrong, but you didn’t really say enough about it to say where it goes wrong.

An efficient and correct approach would be to distribute the $6$ apples over the $3$ colours, enforcing the conditions imposed by the limited supply of apples of each colour using inclusion–exclusion:

$$ \binom{6+2}2-\binom{6-(3+1)+2}2-\binom{6-(4+1)+2}2-\binom{6-(5+1)+2}2=28-6-3-1=18\;, $$

where the first term is the number of ways to distribute $6$ apples over $3$ colours and each of the remaining terms subtracts the number of inadmissible distributions that include more than $3$ red, more than $4$ green and more than $5$ yellow apples, respectively. We don’t have to include the remaining inclusion–exclusion terms because it’s not possible to violate more than one of the supply conditions at the same time.

$\endgroup$
2
  • $\begingroup$ I want to confirm some things. does the 1st term of your equations means : take 8 random apples, from that take 2 to be excluded $\endgroup$ Feb 1, 2020 at 12:47
  • $\begingroup$ @fizqifairuz: No. Are you aware of stars and bars? $\endgroup$
    – joriki
    Feb 1, 2020 at 12:53
2
$\begingroup$

The generating function for the number of ways to arrange $n$ apples is $$ \begin{align} &\left(x+x^2+x^3+x^4\right)\left(x+x^2+x^3+x^4+x^5\right)\left(x+x^2+x^3+x^4+x^5+x^6\right)\\ &=\frac{x-x^5}{1-x}\frac{x-x^6}{1-x}\frac{x-x^7}{1-x}\\ &=\left(x^3-x^7-x^8-x^9+x^{12}+x^{13}+x^{14}-x^{18}\right)\sum_{k=0}^\infty\binom{k+2}{k}x^k \end{align} $$ The coefficient of $x^n$ is $$ \scriptsize\binom{n-1}{n-3}-\binom{n-5}{n-7}-\binom{n-6}{n-8}-\binom{n-7}{n-9}+\binom{n-10}{n-12}+\binom{n-11}{n-13}+\binom{n-12}{n-14}-\binom{n-16}{n-18} $$ which is equal to $$ \scriptsize\binom{n-1}{2}-\binom{n-5}{2}-\binom{n-6}{2}-\binom{n-7}{2}+\binom{n-10}{2}+\binom{n-11}{2}+\binom{n-12}{2}-\binom{n-16}{2} $$ where the sum is only taken over the terms where the upper term is greater than or equal to the lower term.

For $n=9$, we get $$ \binom{8}{2}-\binom{4}{2}-\binom{3}{2}-\binom{2}{2}=18 $$

$\endgroup$
1
$\begingroup$

Let $r\in[0..3]$, $g\in[0..4]$, $y\in[0..5]$ be the number of red, green, yellow apples put in the box after the compulsory three apples. Sorting according to the value of $r$ leads to the following possibilities: $$r=0 \quad\Rightarrow\quad g\in[1..4];\qquad 1\leq r\leq2 \quad \Rightarrow \quad g\in[0..4];\qquad r=3\quad\Rightarrow\quad g\in[0..3]\ ,$$ while $y$ is chosen such that there are $6$ in all. This gives the $18$ found by theory as well.

All this is under the assumption that apples of the same color are not distinguishable. If apples of the same color are distinguishable then we have to choose $9$ apples from $15$ "individual" apples, such that each color appears at least once. This leads to a completely different counting.

$\endgroup$
1
  • $\begingroup$ @N.F.Taussig: You are of course right. I have removed the wrong part, but don't do this other counting unless the OP is asking for it. $\endgroup$ Feb 1, 2020 at 14:55

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.