3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Possible duplicate of Inclusion-exclusion principle: Number of integer solutions to equations $\endgroup$ – Cloverr Feb 2 '16 at 18:27
  • 1
    $\begingroup$ You can also find the coefficient of $x^{20}$ in $(1+x+\ldots + x^8)^3$. Then you get the right answer as well. $\endgroup$ – Henno Brandsma Feb 2 '16 at 18:27
  • $\begingroup$ @Nilanjan thats a different question $\endgroup$ – Zero Feb 2 '16 at 18:31
  • $\begingroup$ Do you have to use inclusion-exclusion? The problem is small enough in scale to permit more straightforward approaches. Heck, even plain enumeration will do. $\endgroup$ – Brian Tung Feb 2 '16 at 18:56
  • $\begingroup$ I've added inclusion-exclusion to my answer. Interestingly, the approach by generating function arrives at the same expression! $\endgroup$ – Brian Tung Feb 2 '16 at 19:03
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The equation $x_1 + x_2 + x_3 = 20$ has only $\binom{22}{20}$ solutions in the non-negative integers. Check your calculations. $\endgroup$ – N. F. Taussig Feb 2 '16 at 18:42
  • $\begingroup$ I replaced $3$ with $20$ erroneously.. $\endgroup$ – Jack's wasted life Feb 2 '16 at 18:45
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One typographical error: In the last sentence of the first paragraph of the inclusion-exclusion argument, you meant $x > 8$ rather than $x > 0$. $\endgroup$ – N. F. Taussig Feb 2 '16 at 20:14
  • $\begingroup$ @N.F.Taussig: Thanks for that. $\endgroup$ – Brian Tung Feb 3 '16 at 18:58
3
$\begingroup$

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

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