Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times.

Question

So I was given this question.

Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times.

First I make $x_1 + x_2 + x_3 = 20$ Then $ 0 \leq x_i \leq 8$

Then we use the Inclusion exclusion principle

Let $A_i$ be the non-negative integer solutions to $x_1 + x_2 + x_3 = 20$ $x_i \geq 9$. Then use inclusion exclusion formula to find $N(A_1 \bigcap A_2 \bigcap A_3)$

What i don't get is how to apply the inclusion exclusion formula. I know the process to get to it but not how to apply it.

Answer 1

Instead of trying to apply formulas take a look at the general theory. Suppose $a_j\le x_j\le b_j$ for $j=1,2,3$.

$$(x^{a_1}+x^{a_1+1}+\cdots+x^{b_1})(x^{a_2}+x^{a_2+1}+\cdots+x^{b_2})(x^{a_3}+x^{a_3+1}+\cdots+x^{b_3})$$

Every solution of $x_1+x_2+x_3=n$ with the constraints $a_j\le x_j\le b_j$ contributes $1$ to the coefficient of $x^n$ in the above expression. So the number of solutions is the coefficient of $x^n$.

Substituting accordingly we see we require the coefficient of $x^{20}$ in $$ (1+x+\cdots+x^8)^3={(1-x^9)^3\over (1-x)^3} $$ or equivalently in $$ (1-3x^9+3x^{18})\sum_{k=0}^{20}\binom{2+k}{k}x^k $$ which equals $$ \binom{22}{20}-3\binom{13}{11}+3\binom{4}{2} $$

Answer 2

There are $15$ different ways to select $20$ coins of three different types, with no type having more than $8$ specimens.

There are a number of different methods to obtain this number. One is to condition on the number of coins of Type $1$. If there are $4$ coins of Type $1$, then there is only one way to obtain $16$ coins of the other two types; if there are $5$ coins of Type $1$, then there are two ways to obtain $15$ coins of the other two types; and so on. $1+2+3+4+5 = 15$.

Another way is to consider that the solutions are the intersection of the lattice cube $\{(x, y, z)) \in \mathbb{N}_{\geq 0}^3 \mid 0 \leq x, y, z \leq 8\}$ with the plane $x+y+z = 20$. If you have any facility with this, you will notice that the intersection is a triangular lattice of side $5$, so the number of solutions is the $5$th triangular number, $15$.

ETA: Finally, we can use inclusion-exclusion, although I find it less straightforward. The number of non-negative integer solutions to $x+y+z = 20$ is, by the usual stars-and-bars approach, $\binom{22}{2} = 231$. However, this counts solutions where at least one of $x, y, z > 8$. The number of solutions where $x > 8$ is, again by stars-and-bars, $\binom{13}{2} = 78$, and there are three coin types, so we must subtract $3 \times 78 = 234$ to obtain $-3$.

Again, however, this double-counts three cases where at least two of $x, y, z > 8$. There are $\binom{4}{2} = 6$ ways in which both $x, y > 8$, but there are three different pairs of coin types, so we must add back $3 \times 6 = 18$ to get $15$. There are no ways to have $x, y, z > 8$ and still add up to $20$, so $15$ is the final result. Note, interestingly, that this is the same expression that Jack's wasted life arrived at, although that method was by way of generating functions.

Answer 3

Let $8-x_i=:y_i$ $(1\leq i\leq3)$. Then we want all $y_i\geq0$ and $y_1+y_2+y_3=4$. There are $${4+3-1\choose 3-1}={6\choose 2}=15$$ ways to choose admissible $y_i$.