A man is selling $15$ different items, and has exactly $3$ of each item. They all cost the same and we have enough to buy $7$ items in total. How many combinations of items can we buy? I know that if he had unlimited of each item, the formula would be ${n+k-1\choose k}$, so ${15+7-1\choose 7}$ or choose ${21\choose 7} = 116280$, but I am not sure how to implement the restriction of only being allowed up to $3$ of each item.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If we let $x_j$ denote the number of items of the $j$th type, $1 \leq j \leq 15$, that are selected, then $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 7 \tag{1}$$ A particular solution of the equation in the nonnegative integers corresponds to the placement of $15 - 1 = 14$ addition signs in a row of seven ones. For instance, $$1+ + + + + + 1 + + + + 1 1 1 + + + 1 1 +$$ corresponds to the solution $x_1 = 1$, $x_2 = x_3 = x_4 = x_5 = x_6 = 0$, $x_7 = 1$, $x_8 = x_9 = x_{10} = 0$, $x_{11} = 3$, $x_{12} = x_{13} = 0$, $x_{14} = 2$, $x_{15} = 0$. The number of such solutions is the number of ways we can place $14$ addition signs in a row of seven ones, which is $$\binom{7 + 15 - 1}{15 - 1} = \binom{21}{14} = \binom{21}{7}$$ as you found.
From these, we wish to subtract those solutions in which one or more variables exceeds $3$ since there are only three items of each type. Observe that it is possible for only of the variables to exceed $3$ since $2 \cdot 4 = 8 > 7$.
Choose which variable exceeds $3$. Suppose it is $x_1$. Then $x_1' = x_1 - 4$ is a nonnegative integer. Substituting $x_1' + 4$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 4 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} & = 7\\ x_1' + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} & = 3 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{3 + 15 - 1}{15 - 1} = \binom{17}{14} = \binom{17}{7}$$ solutions. Hence, there are $$\binom{15}{1}\binom{17}{14}$$ solutions that violate the restriction that no variable exceeds $3$.
Hence, the number of admissible selections is $$\binom{21}{14} - \binom{15}{1}\binom{17}{14}$$
answered Jan 31, 2019 at 11:23
$\begingroup$
$\endgroup$
2
This is a stars and bars problem.
We are allocating 7 purchases over 15 choices. Then use inclusions exclusion to subtract away the cases we chose more than 3 of any one item.
${21\choose 7} - 15\cdot{21-4\choose 3}$
-
$\begingroup$ Would this work for other numbers? Like if he had 4 of each item, would the far right be choose(21-3, 4), with everything else the same? $\endgroup$ Jan 31, 2019 at 0:21
-
$\begingroup$ if there were 4 of each item there would be fewer to exclude. $15\cdot{21-5\choose 7-5}$ $\endgroup$– Doug MJan 31, 2019 at 16:04