How is the formula for counting multisets derived?

Question

I came across a formula that states that the number of ways to make a multiset of cardinality $n$ can be formed from a set of cardinality $k$ is $\binom{n + k - 1}{n}$. How exactly is this derived?

Answer 1

The number of ways we can select $n$ objects from $k$ types of objects is the number of solutions of the equation $$x_1 + x_2 + \ldots + x_k = n \tag{1}$$ in the nonnegative integers. A particular solution of equation 1 corresponds to the insertion of $k - 1$ addition signs in a row of $n$ ones.

For example, suppose $n = 12$ and $k = 6$. Then $$1 1 + 1 1 1 + 1 + + 1 1 1 1 + 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 3$, $x_3 = 1$, $x_4 = 0$, $x_5 = 4$, and $x_6 = 2$.

Therefore, the number of solutions of equation 1 is equal to the number of ways we can insert $k - 1$ addition signs in a row of $n$ ones, which is $$\binom{n + k - 1}{k - 1}$$ since we must choose which $k - 1$ of the $n + k - 1$ positions required for $n$ ones and $k - 1$ addition signs will be filled with addition signs. Alternatively, we obtain the formula $$\binom{n + k - 1}{n}$$ by selecting which $n$ of the $n + k - 1$ positions required for $n$ ones and $k - 1$ addition signs will be filled with ones.

Answer 2

There is a bijection between $k$-element multisets with elements in $\{1, \ldots, n\}$ and $k$-element ordinary sets with elements in $\{1, \ldots, n + k - 1\}$ (of which there are of course $\binom{n + k - 1}{n}$): write the elements in the multiset in (non-strictly) ascending order $x_1 \leq x_2 \leq \cdots \leq x_k$ and then take $\{x_1, x_2 +1, x_3 + 2, \ldots, x_k + k - 1\}$. It's easy to reverse this construction to get the multiset from the ordinary set.

As a side note, there's a similar argument for counting non-strictly ascending functions $f: \{1, \ldots, k\} \to \{1, \ldots, n\}$ (each given by a sorted $k$-element multiset drawn from $\{1, \ldots, n\}$): there's a bijection with strictly ascending functions $g: \{1, \ldots, k\} \to \{1, \ldots, n + k -1 \}$ (each given by a sorted $k$-element set drawn from $\{1, \ldots, n_k-1\}$ given by $g(i) = f(i) + i - 1$ and conversely $f(i) = g(i) - i + 1$.