§ Stars and bars by direct bijection

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

§ The usual proof: stars and bars

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

§ Direct bijection.

To build a direct bijection, map a kk multiset of nn into a kk subset of n+k1n+k-1, which is counted by (n+k1k)\binom{n+k-1}{k}.
  • We are first given a k=6k=6 multiset of n=3n=3, say m={3,1,2,1,3,3}m = \{3, 1, 2, 1, 3, 3\} (mm for multiset).
  • We make the representation unique by imposing an ascending order, so we write M=[1,1,2,3,3]M = [1, 1, 2, 3, 3], where each M[i]M[i+1]M[i] \leq M[i+1].
  • Now, we map the above sequence to a set of unique values, by mapping N[i]=M[i]+iN[i] = M[i] + i. Since M[i]M[i+1]M[i] \leq M[i+1] we have thatM[i]+i<M[i+1]+(i+1)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}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}N = \{ 4, 3, 2, 6, 7, 8 \}, order in ascending order to getN=[2,3,4,6,8]N' = [2, 3, 4, 6, 8] and then subtract ii from N[i]N'[i] to get [20,31,42,63,74,85]=[2,2,2,3,3,3][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 k1k-1 to the final index, and the largest number we can have is nn so we need n+(k1)n + (k-1) values. We need a size kk multiset, making us need (n+(k1)k)\binom{n+(k-1)}{k}.
  • Reference: Bijective Combinatorics