2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.