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.

  • $\begingroup$ 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. $\endgroup$ – Fimpellizieri Sep 6 '16 at 4:56
  • $\begingroup$ @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. $\endgroup$ – soueuls Sep 6 '16 at 5:16
  • $\begingroup$ Same here, Richard Brualdi isn't it? I too had trouble understanding the proof. $\endgroup$ – 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.

  • $\begingroup$ 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 ? $\endgroup$ – soueuls Sep 6 '16 at 5:30
  • $\begingroup$ @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 ... $\endgroup$ – Brian M. Scott Sep 6 '16 at 5:36
  • $\begingroup$ ... given slot and not which ones we have. $\endgroup$ – Brian M. Scott Sep 6 '16 at 5:36
  • $\begingroup$ This makes a lot more sense, thank you. $\endgroup$ – soueuls Sep 6 '16 at 5:44
  • $\begingroup$ @Swann: You’re welcome. $\endgroup$ – Brian M. Scott Sep 6 '16 at 5:45

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.