1
$\begingroup$

Additionally, at least one but not more than 5 boxes of each type are chosen? I was told to solve i.t.o boxes.

I know this question was asked before but none of the answers helped and no work was shown. Here's my thought process..

If I think in terms of boxes, I let $e_i$ be the number of boxes I picked from the $ith$ type. I will have a total of $15$ boxes. I know that I need to pick $1$ box of each kind and no more than $5$. That leaves me with the following: $e_1 + e_2 + e_3 + e_4 + e_5+ e_6 + e_7 = r$ where $e_i$ ranges from $1$ to $5$. Translating it into an integer equation I have the following: $g(x)= (x^1+x^2+x^3+x^4+x^5)^7$, I also know that I need to figure out the coefficient of $x$ raised to the $15$. Now I can try to calculate all the formal products but this seems rather inefficient ..if that is the only way to solve, what's a good method/way to verify I have all possible formal products. Thank you in advance.

$\endgroup$
2
$\begingroup$

You have realized the problem is equivalent to finding the number of integer solutions of equation

$e_1 + e_2 + e_3 + e_4 + e_5+ e_6 + e_7 = 15$ where $1 \leq x \leq 5$

The next step is to actually find the number of solutions. Realize that you can visualize this as putting 15 balls in a row and insert 6 sticks in the holes between each balls to group them into 7 groups, each of which correspond to an $e_i$. It gives ${14 \choose 6}$ solutions.

However you need to get rid of the solutions where $e_i \geq 6$. What you do here is you take 5 balls away and find the number of solutions to equation

$e_1 + e_2 + e_3 + e_4 + e_5+ e_6 + e_7 = 10$

Then when you put the 5 balls back to any of the 7 $e_i$s you will get a solution with at least one $e_i \geq 6$. The nice thing about 15 is that you cannot have any solution with two or more $e_i \geq 6$ so you do not need to worry about duplications.

Hence the final answer is simply ${14 \choose 6} - 7\times{9 \choose 6} = 2415$.

In general, if the number of balls is larger than 15 so that two or more $e_i \geq 6$ becomes possible, you will need to add back the two $e_i \geq 6$ cases and minus back the three $e_i \geq 6$ cases and so on.

For example if $r = 20$ instead of $r = 15$, then you need to use ${19 \choose 6} - {7 \choose 1}\times{14 \choose 6} + {7 \choose 2}\times{9 \choose 6}$.

$\endgroup$
  • $\begingroup$ why do you take 5 balls away from 15 to account for groups that might have gotten 6 balls or more? $\endgroup$ – ponderingdev Sep 29 '15 at 2:46
  • $\begingroup$ In your first equation, $0 \leq x \leq 5$ should read $1 \leq e_i \leq 5$ for $i = 1, 2, 3, \ldots, 7$ since there are a positive number of each type of chocolate. $\endgroup$ – N. F. Taussig Sep 29 '15 at 2:53
  • $\begingroup$ Sorry for the confusion, 0 was a typo and was supposed to be 1. $\endgroup$ – cr001 Sep 29 '15 at 3:11
  • $\begingroup$ @curiousmind1995 Thinking in terms of numeric solutions will probably be easier to understand for this part. The second equation generates solutions with $e_i \geq 1$ such that they add up to 10. If you add 5 to any of $e_i$, you will get a number at least 6 and all the numbers will add up to 15. $\endgroup$ – cr001 Sep 29 '15 at 3:14
  • $\begingroup$ Okay I think I get it but why 9 choose 6. wouldn't be 10 choose 6. I get why you multiply times 7, because you have 7 options for which bin could have 6 or more balls. $\endgroup$ – ponderingdev Sep 29 '15 at 13:50
1
$\begingroup$

We wish to select $15$ boxes of chocolate from seven different types of boxes, where at least one of each type and no more than five of each type is selected. Since at least one box of each type of box is selected, we can first select those seven boxes. That leaves us with eight boxes to select. Let $x_k$ denote the number of boxes of type $k$ that we select after we first select one box of each type. Then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 8 \tag{1}$$ Equation 1 is an equation in the nonnegative integers. The number of solutions of equation 1 is the number of ways we can insert six addition signs in a row of eight ones, which is $$\binom{8 + 6}{6} = \binom{14}{6}$$ since we must select which six of the fourteen symbols (eight ones and six addition signs) are addition signs.

However, we must not select more than five boxes of one type. Since we have already selected one of each type, $x_k \leq 4$ for $1 \leq k \leq 7$. Suppose $x_1 \geq 5$. Let $y_1 = x_1 - 5$. Then $y_1$ is a nonnegative integer. Substituting $y_1 + 5$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 5 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 & = 8\\ y_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 & = 3 \end{align*} which is an equation in the nonnegative integers with $$\binom{3 + 6}{6} = \binom{9}{6}$$ solutions. Since there are $\binom{7}{1}$ ways of selecting a particular type of box more than five times, the number of ways we can select more than five boxes of one type is $$\binom{7}{1}\binom{9}{6}$$ It is not possible to select more than five boxes of two or more types of chocolate while selecting at least one of each type. Hence, the number of ways of selecting $15$ boxes of chocolate of seven types with at least one and at most five of each type is $$\binom{14}{6} - \binom{7}{1}\binom{9}{6}$$

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