I am having a hard time in understanding the following theorem:
Let $S$ be a multiset with objects of $k$ types, each with an infinite repetition number. Then the number of r-combinations of $S$ equals
$${r+k-1 \choose r} = {r+k-1 \choose k-1}$$
Proof:
Let the $k$ types of objects of $S$ be $a_1,a_2,…,a_k$ so that
$$S = \{\infty.a_1,\infty.a_2,…,\infty.a_k\}$$
Any r-combination of $S$ is of the form $\{x_1.a_1,x_2.a_2,…,x_k.a_k\}$, where $x_1,x_2,…,x_k$ are nonnegative integers with $x_1,x_2,…,x_k = r$ Conversely, every sequence $x_1,x_2,…,x_k$ of nonnegative integers with $x_1,x_2,…,x_k = r$ corresponds to an r-combination of $S$. Thus, the number of r-combinations of $S$ equals the number of solutions of the equation
$$x_1+x_2+…+x_k = r$$
We show that the number of these solutions equals the number of permutations of the multiset
$$T = \{r.1, (k-1).*\}$$
I don't understand how the equation relates to the number of permutations of the set $T$ and how the $T$ has been constructed.
Best Answer
$T$ is a multiset that has $r+k-1$ members. These members are of two types: some of them are ones, and some of them are asterisks. Specifically, the multiset $T$ contains $r$ ones and $k-1$ asterisks.
To see how permutations of this multiset are related to solutions to $x_1+\ldots+x_k=r$ in non-negative integers $x_1,\ldots,x_k$, let’s look at a specific example, say $k=5$ and $r=10$. Here are three permutations of the multiset $T=\{10\cdot1,4\cdot*\}$:
$$\begin{align*} &111*11**1111*1\\ &1*11*111*1111*\\ &11*11*11*11*11 \end{align*}\tag{1}$$
The $4$ asterisks leave $5$ spaces for ones: one before the first asterisk, $3$ between consecutive asterisks, and one more after the last asterisk. These $5$ spaces correspond to the $5$ variables $x_1,x_2,x_3,x_4$, and $x_5$, and the number of ones in each space corresponds to the actual value of the variable. Thus, the three permutations of $T$ shown in $(1)$ correspond respectively to the solutions
$$\begin{align*} &3+2+0+4+1=10\\ &1+2+3+4+0=10\\ &2+2+2+2+2=10\;. \end{align*}\tag{2}$$
Going in the other direction, the solution $0+0+3+5+2=10$ corresponds to the permutation $**111*11111*11$ of $T$.
In general you will have $k-1$ asterisks; there is one space for ones before the first asterisk, one after the last asterisk, and $k-2$ between consecutive asterisks for a total of $k$ spaces, one for each variable. The number of ones in the first space corresponds to the value of $x_1$, the number in the second space to the value of $x_2$, and so on. Since we have $r$ ones, each permutation of $T$ will automatically yield a solution in non-negative integers to $x_1+\ldots+x_k=r$, since we distribute $r$ ones amongst $k$ spaces available to hold them. Conversely, each solution to the equation can be understood as describing a unique permutation of $T$ via this same correspondence.