$r-$ combinations of multisets

Question

I have the topic $r-$ combinations of multisets in my notes

Let $S=\{\infty a_1,\infty a_2,\ldots ,\infty a_k\}$ ,
then the formula for the $r-$*combinations of S* is given as:
$$\binom{r+k-1}{k-1}$$

but I don't know how did we reach the formula...
Please help me with this...

Answer 1

I think you're simply talking about the multinomial coefficient. You can find a good derivation on Wikipedia's Stars and Bars site.

Answer 2

$r$- combinations of multisets

You can refer it in "Prinicples and Techniques in Combinatorics", an excellent introductory book on combinatorics written by Chen Chuan-chong and Koh Khee-Meng.

I shall reproduce it for you. We can represent each $r$-combination of $M$ by considering each $a_i$ as a box. For example, the $10$-combination $\{3\cdot a_1,2\cdot a_2,0\cdot a_3,\cdots,5\cdot a_k\}$ can be interpreted as the binary sequence $00010011\cdots100000$ as shown below. (We used $1$ as a separator between boxes)

$a_1 \;\; |\; a_2 \; | \; a_3 |\; \cdots\; | \;a_k$

$000 \; 1 \; 00 \;\; 1 \;\;\;\;\; 1 \cdots \;\;\;1\; 00000$

This is indeed a bijection and hence the number of $r$-combinations of $M$ is same as the the number of binary sequences of length $r+(n-1)$ [here, $n-1$ stands for the separator $1$'s] containing $(n-1)$ number of $1$'s. The latter is $C(r+n-1,n-1)$.