In how many different ways can apples be placed in the box if at least there is one apple of each color?

Question

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).

Answer 1

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.

Answer 2

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

Answer 3

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.