How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies?

Question

A cookie store sells 6 varieties of cookies. It has a large supply of each kind. How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies?

For my answer, I put $6 \cdot 6 \cdot 5^{13}$. My logic was to assume that the first two are sugar cookies, so there are only $5$ choices for the next $13$ cookies, but I am not sure if this is correct.

Answer 1

This to some degree can be reasonably done with three cases: The case where there are $i$ sugar cookies picked, $i \in [2] \cup \{0\}.$ Let's consider this case in a general sense. We see that in this case, I can set $i$ of the $15$ cookies to be sugar cookies $1$ way. for the remaining $15-i$ cookies, I have $5$ other possible cookies to choose. However, given that order does not matter, I cannot simply do $5^{15-i}$ since this can lead to instances where I double-count the same instance. Thus, this becomes a classic "stars and bars" problem where I have 5 columns for each of the five cookies and $15-i$ places to disperse for them. This becomes the value $\binom{15 - i + 5 -1}{15 - i} = \binom{19 - i}{15 - i} = \binom{19-i}{4}.$ Thus, given the rule of products, the number of ways I can select $15$ cookies given that $i$ of them are sugar cookies is $1 \times \binom{19-i}{4} = \binom{19-i}{4}$. Thus, by rule of sums, the number of ways I can select $15$ cookies given that at most $2$ of them can be sugar cookies is

$$\sum_{i=0}^2 \binom{19-i}{4} = 9316.$$

Answer 2

Let $x_k$ be the number of cookies of type $k$, $1 \leq k \leq 6$. Since an order of $15$ cookies is placed, $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 15 \tag{1}$$ where equation 1 is an equation in the non-negative integers. A particular solution to equation 1 corresponds to the placement of five addition signs in a row of fifteen ones. For instance, $$1 1 1 + + 1 1 1 1 + 1 + 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 0$, $x_3 = 4$, $x_4 = 1$, $x_5 = 2$, $x_6 = 5$. Thus, the number of solutions of equation 1 is the number of ways five addition signs can be inserted into a row of fifteen ones, which is $$\binom{15 + 5}{5} = \binom{20}{5}$$ since we must choose which five of the twenty symbols (five addition signs and fifteen ones) will be addition signs.

However, we have to exclude those orders in which more than two sugar cookies are selected. We must subtract the number of orders in which more than two sugar cookies are selected from the total.

Suppose $x_1$ denotes the number of sugar cookies in the order. If $x_1 > 2$, then $y_1 = x_1 - 3$ is a non-negative integer. Substituting $y_1 + 3$ for $x_1$ in equation 1 yields \begin{align*} y_1 + 3 + x_2 + x_3 + x_4 + x_5 + x_6 & = 15\\ y_1 + x_2 + x_3 + x_4 + x_5 + x_6 & = 12 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers with $$\binom{12 + 5}{5} = \binom{17}{5}$$ solutions.

Subtracting the number of orders in which more than two sugar cookies are selected from the total number of ways of ordering fifteen cookies selected from the six varieties at the shop yields $$\binom{20}{5} - \binom{17}{5}$$

Why is your solution incorrect?

1. There are six varieties of cookies, of which just one is sugar cookies. Thus, there is one way of selecting a sugar cookie, not six.
2. An order can contain up to two sugar cookies. You assumed that two were selected.
3. If two sugar cookies are selected, they can be selected anywhere in the order. They do not need to be selected in the first two positions.
4. By multiplying the number of ways of ordering two sugar cookies by $5^{13}$, you were counting ordered selections. However, the order in which the cookies are ordered is irrelevant.