3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ When you count the number of ways to distribute with each student getting at least three, it should be $\binom{13+4-1}{4-1}$ using the stars and bars method. $\endgroup$ – Nicholas Nov 15 '15 at 9:37
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is very very awesome !! Thank you so much :D $\endgroup$ – Wongsakorn Nov 16 '15 at 12:37
  • $\begingroup$ But after equation one, you see it should be (11) choose (3) right ?? not 12 choose 3 $\endgroup$ – Wongsakorn Nov 16 '15 at 14:03
  • $\begingroup$ You are quite correct. That was a remnant of an initial incorrect attempt, which I failed to edit properly. $\endgroup$ – N. F. Taussig Nov 16 '15 at 14:08
1
$\begingroup$

Add $3$ pencils to your $25$ pens. Distribute the $28$ by giving each of the four people $7$ writing implements; this will result in them each getting no more than $7$ pens. The number of ways of doing this is the number of ways of distributing the pencils so everybody get at least $3$ pens, i.e. no more than $7-3=4$ pencils (not a problem as there only are $3$ pencils), which is ${3+4-1 \choose 4-1} ={6 \choose 3}= 20$.

An alternative approach to your original problem is to use a generating function, so you are looking for the coefficient of $x^{25}$ in the expansion of $$(x^3+x^4+x^5+x^6+x^7)^4.$$

Your idea of distributing the minimum $3$ each to the four people is similar to taking out the factor of $x^3$ to give $x^{12}(1+x+x^2+x^3+x^4)^4$ or looking for the coefficient of $x^{13}$ in the expansion of $$(1+x+x^2+x^3+x^4)^4.$$ You could work this out directly. My pencil approach is similar to noting that by symmetry this is also the coefficient of $x^{4\times 4 - 13}=x^3$, which is easier to work with.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have done generating function already, I would like to know the method of using the Combinatorics, thank you but sorry I don't quite get what you say in above paragraph. Why do we have to add pencil. Is it possible to use the inclusion-exclusion ? $\endgroup$ – Wongsakorn Nov 15 '15 at 10:19
  • $\begingroup$ @Wongsakorn Adding the pencils gets to the answer more quickly, in this particular case. $\endgroup$ – Henry Nov 15 '15 at 22:35
0
$\begingroup$

This is a typical example of string and gap method now we want to distribute pens in a way $3<x<7$. The general solution is $(n+k-1)C(k-1)$, so putting three strings creates four gaps so number of ways are $(3+4-1)C(4-1)$ so ways are $6C3=20$. Hope this helps you.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your answer wasn't rendered properly because it contained a < outside math (or code) mode. The parser considered it the start of a (malformed) HTML tag therefore. To avoid that, never have < outside math (or code) mode in your posts. $\endgroup$ – Daniel Fischer Nov 16 '15 at 15:56

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.