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)?

  • 3
    $\begingroup$ The usual stars and bars argument is about as simple as anything. $\endgroup$ Apr 14, 2015 at 15:54
  • $\begingroup$ 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. $\endgroup$ Apr 14, 2015 at 17:09
  • $\begingroup$ Dear @MarcvanLeeuwen, I edited. Thank you. $\endgroup$ Apr 14, 2015 at 19:06

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.