Number of coefficients of a multivariable polynomial

Question

Let $g \in \mathbb{F}[x_1, \dots, x_n]$ be a polynomial of degree $d$ with $n$ variables. Number of its coefficients is ${n+d \choose d}$

Is there an easy proof? It clearly holds for univariate polynomial $n=1$. It holds even for some polynomials I tried, for example $g(x,y) = x^3 + y^3 + x^2y + y^2x + y^2 + xy + x^2 + x + y + 1$, where $10 = {2+3 \choose 3}$.

Answer 1

This can be proved via a stars and bars argument. Say we have $k$ stars and we want to put them in $n$ bins, with some bins possibly empty. Theorem 2 in the article proves that the number of such arrangements is $$\binom{n+k-1}{k}.$$

We will show that the number of possible monomials of $n$ variables and degree $\le k$ is equal to the number of possible arrangements of $k$ stars and $n + 1$ bins, with some bins possibly empty.

Let the first $n$ bins correspond to the powers of the variables $x_1, x_2, \ldots, x_n$, and ignore the last bin. The total number of stars in the first $n$ bins is $\le k$. This produces all possible monomials of $n$ variables and degree $\le k$. Per the first paragraph, the number of arrangements is:

$$ \binom{(n+1) + k - 1}{k} = \binom{n + k}{k} $$

Answer 2

If you write out a monomial, you can order the variables increasingly, and prefix by a power of $1$ so that the total exponent becomes$~d$. Now if you write explicit multiplications before each power, and then spell out powers by repetitions (without multiplication signs), you get a string of $n+d$ symbols. For instance with variables $a,b,c,d,e$, the monomial $a^3bc^2e^4$ viewed as monomial of degree at most $d=12$ becomes $11\times aaa\times b\times cc\times\times eeee$. It looks a bit strange, and the initial $11$ represents $1^2$ rather than eleven.

You can now check that the monomial is uniquely determined by the positions of its $n$ multiplication signs (here $n=5$) in the string of length $n+d$, and that every set of positions corresponds to a monomial. Their total number is therefore $\binom{n+d}n=\binom{n+d}d$.

Equivalently, maybe a bit more naturally, and in any case in accordance with my general principle when interpreting binomial coefficients to always try to do so in terms of lattice paths, the following description can be given. Associate to a monomial $x_1^{e_1}x_2^{e_2}\ldots x_n^{e_n}$ with $e_1+e_2+\cdots+e_n\leq d$ a path from $(0,0)$ to $(x,n)$ using only steps to the right and upwards, by the requirement that there be exactly $e_i$ horizontal steps at level$~i$ (leaving $d-(e_1+\cdots+e_n)$ horizontal steps at level$~0$). For a given monomial this is possible in only one way, and there are $\tbinom{n+d}d$ different paths, each corresponding to a monomial.