[Math] In how many ways can $25$ identical pens be distributed to four students with restrictions

discrete mathematics

Use combinatorics to count how many ways can 25 identical pens be distributed to four students so that each student gets at least three but no more than seven pens.

What I have done so far is look like it make sense but it doesn't work out

I was thinking about view it as bit string of 0 and 1.
I put 3 pens for each student first so I left with 13 pens(o's)
Now I try to distribute these 13 pens. And found out that there is 13 Choose 4 = 715 ways. But now when I'm trying to excluded the ways in which there is student who got more than 7 pens. I supposed to get 705 because (when I use the generating function method I got result 10, so if 715-705 = 10 this will be correct)but I can't find the way that this will work out.

Best Answer

As you observed, we can first distribute three pens to each of the four students, leaving $13$ additional pens to be distributed to the four students. The restriction that no student receive more than seven pens means that no student can receive more than four additional pens. Let $x_k$ be the number of additional pens received by the $k$th person. Then we must solve the equation $$x_1 + x_2 + x_3 + x_4 = 13 \tag{1}$$ in the non-negative integers subject to the restrictions that $x_k \leq 4$ for $1 \leq k \leq 4$. A particular solution of equation 1 in the non-negative integers is determined by where we place three addition signs in a row of thirteen ones. For instance, $$1 1 1 1 + 1 1 + 1 1 1 1 1 1 1 1 +$$ corresponds to the solution $x_1 = 4$, $x_2 = 2$, $x_3 = 8$, and $x_4 = 0$, while $$1 1 1 + 1 1 1 1 + 1 1 1 1 1 + 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 4$, $x_3 = 5$, and $x_4 = 1$. The number of such solutions is equal to the number of ways we can select which three of the sixteen symbols (three addition signs and thirteen ones) will be addition signs, which is $$\binom{13 + 3}{3} = \binom{16}{3}$$ From these, we must subtract those solutions in which one or more of the variables exceeds $4$. Since $3 \cdot 5 = 15 > 13$, at most two two of the variables can exceed $4$.

Suppose $x_1 > 4$. Let $y_1 = x_1 - 5$. Then $y_1$ is a non-negative integer. Substituting $y_1 + 5$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 5 + x_2 + x_3 + x_4 & = 13\\ y_1 + x_2 + x_3 + x_4 & = 8 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers. The number of solutions of equation 2 is the number of ways we can select which three of twelve symbols (three addition signs and eight ones) will be addition signs, which is $$\binom{8 + 3}{3} = \binom{11}{3}$$ Since there are four ways one of the variables could exceed four, there are $$\binom{4}{1}\binom{11}{3}$$ ways of distributing more than four pens to at least one person.

Suppose $x_1 > 4$ and $x_2 > 4$. Let $y_1 = x_1 - 5$; let $y_2 = x_2 - 5$. Substituting $y_1 + 5$ for $x_1$ and $y_2 + 5$ for $x_2$ in equation 1 yields \begin{align*} y_1 + 5 + y_2 + 5 + x_3 + x_4 & = 13\\ y_1 + y_2 + x_3 + x_4 & = 3 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers with $$\binom{3 + 3}{3} = \binom{6}{3}$$ solutions. Since there are $\binom{4}{2}$ ways two of the four variables could exceed four, there are $$\binom{4}{2}\binom{6}{3}$$ distributions of pens in which at least two people receive more than four pens.

By the Inclusion-Exclusion Principle, the number of ways we can distribute $25$ pens to four people so that each person receives at least three and at most seven pens is $$\binom{16}{3} - \binom{4}{1}\binom{11}{3} + \binom{4}{2}\binom{6}{3}$$

Alternate Solution: A more efficient method than using the Inclusion-Exclusion Principle to solve equation 1 subject to the restrictions $x_k \leq 4$ for $1 \leq k \leq 4$ is to let $z_k = 4 - x_k$ for $1 \leq k \leq 4$. Then $0 \leq z_k \leq 4$ for $1 \leq k \leq 4$. Substituting $4 - z_k$ for $x_k$, $1 \leq k \leq 4$, in equation 1 yields \begin{align*} 4 - z_1 + 4 - z_2 + 4 - z_3 + 4 - z_4 & = 13\\ -z_1 - z_2 - z_3 - z_4 & = -3\\ z_1 + z_2 + z_3 + z_4 & = 3 \tag{4} \end{align*} Equation 4 is an equation in the non-negative integers with $$\binom{6}{3}$$ solutions.

Related Question