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$

2 Answers 2

1
$\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$
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$
2
  • $\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 M
    Jan 31, 2019 at 16:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .