§ Stars and bars by direct bijection

We know that the number of $k$ element multisets using letters from $\{1, \dots, n\}$ is $\binom{k+n-1}{k}$. That is, we are allowed to pick elements from $\{1, \dots, n\}$ repeatedly, and we want $k$ such elements.

§ The usual proof: stars and bars

The usual proof involves creating $k$ "stars" ( $\star$) which need to be placed in $n$ buckets. These buckets are created by having $(n-1)$ "bars" ( $|$). For example, if we wish to consider all $k=3$ element multisets of the letter $n=4$: $\{w, x, y, z\}$:

§ Direct bijection.

To build a direct bijection, map a $k$ multiset of $n$ into a $k$ subset of $n+k-1$, which is counted by $\binom{n+k-1}{k}$.

• We are first given a $k=6$ multiset of $n=3$, say $m = \{3, 1, 2, 1, 3, 3\}$ ( $m$ for multiset).
• We make the representation unique by imposing an ascending order, so we write $M = [1, 1, 2, 3, 3]$, where each $M[i] \leq M[i+1]$.
• Now, we map the above sequence to a set of unique values, by mapping $N[i] = M[i] + i$. Since $M[i] \leq M[i+1]$ we have that $M[i] + i < M[i+1] + (i+1)$.
• This gives us the set $M' = \{ 1+0, 1+1, 2+2, 3+3, 3+4 \} = \{ 1, 2, 3, 6, 7 \}$.
• See that this process is reversible. Given some set, say $N = \{ 4, 3, 2, 6, 7, 8 \}$, order in ascending order to get $N' = [2, 3, 4, 6, 8]$ and then subtract $i$ from $N'[i]$ to get $[2-0, 3-1, 4-2, 6-3, 7-4, 8-5] = [2, 2, 2, 3, 3, 3]$.

I found this very elegant, because it "de-multisets" the multiset by adding just enough to make each element unique, and then simply counts the unique subset. Very slick! We need to add $k-1$ to the final index, and the largest number we can have is $n$ so we need $n + (k-1)$ values. We need a size $k$ multiset, making us need $\binom{n+(k-1)}{k}$.

• Reference: Bijective Combinatorics