Combinatorics - Limited Replacement

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.

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

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

• 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? Jan 31, 2019 at 0:21
• if there were 4 of each item there would be fewer to exclude. $15\cdot{21-5\choose 7-5}$ Jan 31, 2019 at 16:04