# How many multisets of length $d$ of a set of $n+1$ elements?

The number of multisets of length $d$ of a set of cardinality $n+1$ is $${n+d}\choose{n}$$

This number is, among other things, the dimension of the vector space of homogeneous polynomials of degree $d$ in the variables $x_0,\ldots,x_n$.

What are the most immediate ways to obtain this? Is there a simple proof by recurrence? What about a less elementary proof which you find particularly elegant (and easy to remember)?

• The usual stars and bars argument is about as simple as anything. Apr 14, 2015 at 15:54
• Something's wrong here. The number of strings of length $d$ over an alphabet of $m$ symbols is $m^d$. Now put $m=n+1$. Multisets are something else. Apr 14, 2015 at 17:09
• Dear @MarcvanLeeuwen, I edited. Thank you. Apr 14, 2015 at 19:06

Since you mention dimension of the space of homogeneous polynomials of degree $d$ in $K[x_0,\ldots,x_n]$, you might appreciate the following point of view.
The Hilbert-Poincaré series of the graded vector space $K[x]$ is clearly $$\sum_{d\in\Bbb N}T^d=\frac1{1-T}=\sum_{d\in\Bbb N}\binom{-1}d(-T)^d.$$ Here as usual binomial coefficients with arbitrary upper index are given by $$\binom nk=\frac{n(n-1)\ldots(n-k+1)}{k!},$$ and those with negative integer upper integer index are related to ordinary ones by $$\binom{-n}k=(-1)^k\binom{n+k-1}k.\tag1$$
Since $K[x_0,\ldots,x_n]\cong K[x]^{\otimes(n+1)}$ as graded vector spaces, it follows that its Hilbert-Poincaré series is $$\left(\frac1{1-T}\right)^{n+1} =\sum_{d\in\Bbb N}\binom{-n-1}d(-T)^d =\sum_{d\in\Bbb N}\binom{n+d}kT^d.$$ Using $n+1$ rather than $n$ is just a trick to make the final answer come out marginally simpler.