3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$

$\endgroup$
  • $\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$ – D. Trampson Jan 31 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 M Jan 31 at 16:04
0
$\begingroup$

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}$$

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