Ok, this might be a stupid question, but I need some clarification on when problems have a direct solution of doing $\binom{n}{r}$ and some when you need to do $\binom{n+r-1}{r}$.
A grocer sells six types of apples. You want to buy a bag of five, with no more than two from each type. How many options do you have?
So $\binom{6}{5}$ would give us the total number of combinations. But from this, we need to subtract combination that has $3$ of one kind. I'm stuck on how to evaluate on that part. Many problems like this say that for calculating the second combination, they do $\binom{6+5-1}{5}$. Why? Isn't the condition asking for no more than $3$? So why choose $5$. And why are we adding $6+5-1$ in the first place if the whole types are just $6$?
The number $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ represents the number of ways of selecting a subset of $k$ elements from a set with $n$ elements.
The number $$\binom{k + n - 1}{n - 1}$$ represents the number of ways of selecting $k$ elements from $n$ types of elements when there are at least $k$ elements of each type.
Let $x_j$, $1 \leq j \leq 6$, be the number of apples of type $j$ that are purchased. Since a total of five apples are purchased, $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 5 \tag{1}$$ Equation 1 is an equation in the nonnegative integers.
A particular solution of equation 1 corresponds to the placement of five addition signs in a row of five ones. For instance, $$1 1 1 + + + 1 + 1 +$$ represents the solution $x_1 = 3$, $x_2 = 0$, $x_3 = 0$, $x_4 = 1$, $x_5 = 1$, $x_6 = 0$, while $$1 + 1 + 1 + 1 + + 1$$ represents the solution $x_1 = 1$, $x_2 = 1$, $x_3 = 1$, $x_4 = 1$, $x_5 = 0$, $x_6 = 1$.
The number of ways five apples can be purchased from six types of apples is $$\binom{5 + 6 - 1}{6 - 1} = \binom{10}{5}$$ since we must choose which five of the ten positions required for five ones and five addition signs will be filled with addition signs.
A particular solution of the equation $$x_1 + x_2 + \cdots + x_n = k$$ in the nonnegative integers corresponds to the placement of $n - 1$ addition signs in a row of $k$ ones. The number of such solutions is $$\binom{k + n - 1}{n - 1}$$ since we must choose which $n - 1$ positions of the $k + n - 1$ positions required for $k$ ones and $n - 1$ addition signs will be filled with addition signs.
We showed above that if there were no restrictions, then there are $$\binom{5 + 6 - 1}{6 - 1} = \binom{10}{5}$$ ways to purchase the apples. From these, we must subtract those cases in which at least three apples of one type are purchased. Notice that it is possible to purchase at least three apples of at most one type since $2 \cdot 3 = 6 > 5$.
There are six ways to choose the type of apple of which at least three are purchased. Suppose it is type 1. Then $x_1' = x_1 - 3$ is a nonnegative integer. Substituting $x_1' + 3$ for $x_1$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 + x_6 = 2 \tag{2}$$ Equation 2 is an equation in the nonnegative integers with $$\binom{2 + 6 - 1}{6 - 1} = \binom{7}{5}$$ solutions.
Hence, there are $$\binom{6}{1}\binom{7}{5}$$ ways to purchase at least three apples of one type.
Thus, the number of ways to buy five apples from six types of apples if no more than two of any one type are purchased is $$\binom{10}{5} - \binom{6}{1}\binom{7}{5}$$