# Number of r-combination of a multiset of with k different types of objects

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.

• I'm guessing $T$ is defined as a multiset with $r$ repetitions of the element $1$ and $(k-1)$ repetitions of the element $*$. That said, the relation between the equation and permutations of $T$ is, judging by the text, to follow what you transcribed. – Fimpellizieri Sep 6 '16 at 4:56
• @Fimpellizieri I was not clear with my question. How to read and understand the multiset T I was trying to ask, following what logic we constructed T the way it is. – soueuls Sep 6 '16 at 5:16
• Same here, Richard Brualdi isn't it? I too had trouble understanding the proof. – vs_292 Feb 12 '18 at 4:54

$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.

• This indeed helped me a lot to understand the relation better. I still have a question though why is this not working: each element of $r$ can increase any $x_i$ by one. Since there are k types of objects I have $k^r$ ways to make a permutation ? – soueuls Sep 6 '16 at 5:30
• @Swann: That would be true if you were distributing $r$ balls numbered $1$ through $r$ amongst $k$ distinguishable boxes. The distribution $1,3*5*2,4$ of $5$ balls amongst $3$ boxes is different from the distribution $1,5*3*2,4$, because the contents of the first two boxes are not the same in the two distributions. However, both of those distributions correspond to the solution $2+1+2=5$ of the equation $x_1+x_2+x_3=5$. Your $k^r$ overcounts, because it treats the individual ones in the multiset $T$ as $r$ distinguishable objects, when in fact all we can ever tell is how many we have in a ... – Brian M. Scott Sep 6 '16 at 5:36
• ... given slot and not which ones we have. – Brian M. Scott Sep 6 '16 at 5:36
• This makes a lot more sense, thank you. – soueuls Sep 6 '16 at 5:44
• @Swann: You’re welcome. – Brian M. Scott Sep 6 '16 at 5:45