[Math] How many ways are there for a child to take 10 pieces of candy with 4 types of candy if the child takes at most 5 pieces of any type of candy

combinatorics

How many ways are there for a child to take 10 pieces of candy with
4 types of candy if the child takes at most 5 pieces of any type of candy?

My solution begins like , $ 10 \choose 4$ is the answer,consistent to $ n-1 \choose r $ as this is similar to finding the number of non-zero positive integer solution of the equation $X_1 + X_2 + X_3 + x_4 = 10$ ,but i dont know how to account for the amount of candy the child takes at most, which is throwing me off.

Best Answer

Let $x_k$ be the number of pieces of candy of type $k$ the child takes. Then we wish to determine the number of solutions in the nonnegative integers of the equation $$x_1 + x_2 + x_3 + x_4 = 10 \tag{1}$$ subject to the restrictions that $x_k \leq 5$ for $1 \leq k \leq 4$.

The number of solutions to equation 1 is equal to the number of ways three addition signs can be placed in a row of $10$ ones, which is $$\binom{10 + 3}{3}$$ since we must choose which three of the thirteen symbols ($10$ ones and $3$ addition signs) are addition signs.

From these, we must eliminate those solutions in which the child takes more than five pieces of candy of one type. Since the child select $10$ pieces of candy, it is not possible for the child to take more than five pieces of more than one type of candy.

Suppose the child takes more than five pieces of candy of type 1. Let $y_1 = x_1 - 6$. Then $y_1$ is a nonnegative integer. Substituting $y_1 + 6$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 6 + x_2 + x_3 + x_4 & = 10\\ y_1 + x_2 + x_3 + x_4 & = 4 \end{align*} which is an equation in the nonnegative integers with $$\binom{4 + 3}{3} = \binom{7}{3}$$ solutions. Since the child could have taken more than five pieces of candy from any of the four types, the number of ways the child can select ten pieces of candy without taking more than five of one type is $$\binom{13}{3} - \binom{4}{1}\binom{7}{3}$$

Related Question