# determine the number of r-combinations of the multiset

Determine the number of r-combinations of the multiset $\{1 \cdot a_1, \infty. \cdot a_2, ... , \infty \cdot a_k \}$.

The answer in the back of the book is $\binom{r+k-2}{k-2}+\binom{r+k-3}{k-2}$.

I see where $\binom{r+k-2}{k-2}$ comes from because it is the number of r-combinations from the multiset that does not include $a_1$. I don't understand where the $\binom{r+k-3}{k-2}$ comes from though.

Let $x_j$ be the number of occurrences of $a_j$, where $1 \leq j \leq k$. Then we need to find the number of solutions of the equation $$x_1 + x_2 + x_3 + \ldots + x_k = r \tag{1}$$ in the nonnegative integers subject to the restriction that $x_1 \leq 1$.

If $x_1 = 0$, equation 1 reduces to $$x_2 + x_3 + \ldots + x_k = r \tag{2}$$ Since there are $k - 1$ terms in the sum, a particular solution of equation 2 corresponds to the placement of $k - 2$ addition signs in a row of $r$ ones. The number of such solutions is $$\binom{r + k - 2}{k - 2}$$ since we must choose which $k - 2$ of the $r + k - 2$ positions for $r$ ones and $k - 2$ addition signs will be filled with addition signs.

If $x_1 = 1$, equation 1 reduces to $$x_2 + x_3 + \ldots + x_k = r - 1 \tag{3}$$ In this case, a particular solution of equation 3 corresponds to the placement of $k - 2$ addition signs in a row of $r - 1$ ones. The number of such solutions is $$\binom{r - 1 + k - 2}{k - 2} = \binom{r + k - 3}{k - 2}$$ since we must choose which $k - 2$ of the $r - 1 + k - 2 = r + k - 3$ positions for $r - 1$ ones and $k - 2$ addition signs will be filled with addition signs.

Since the two cases are mutually exclusive and exhaustive, the number of solutions of equation 1 is found by adding the results for equations 2 and 3.

As per the question, each element ranging from 'a2' to 'ak' can be included infinite number of time in 'r-combination' so produced, but element 'a1' can be included only once if required.

So now consider the following two cases :

Case 1 : If 'a1' is included in r-combination :

Then find number of ways of producing 'r-1'-combination from left 'k-1' elements which is equal to second term (r+k-3)C(k-2).

Case 2 : If 'a1' is not included in r-combination :

Then find number of ways of producing 'r'-combination from left 'k-1' elements which is equal to first term (r+k-2)C(k-2).

Summation of results produced in two cases produces final answer.