The number of monomials of a given degree

Question

I'm trying to understand why the number of the monomials of degree $d$ in $n+1$ variables is $C_{n+d,n}$. If someone could help me to remember how to solve this, I would be glad.

Thanks.

Answer 1

The stars and bars argument in combinatorics shows that the number of ways to place $d$ indistinguishable objects (stars) in $n + 1$ distinguishable boxes is to lay the objects in a line and place barriers (bars) to establish boundaries between the boxes.

Here's an example of the bijection with $d = 3$ and $n = 2$.

$$ \begin{align} x_1^3 & \longleftrightarrow \star \star \star \;| \;| \\ x_1^2 x_2 & \longleftrightarrow \star \star \,| \star | \\ x_1^2 x_3 & \longleftrightarrow \star \star \,| \;| \star \\ x_1 x_2^2 & \longleftrightarrow \star \;| \star \star \;| \\ x_1 x_2 x_3 & \longleftrightarrow \star \;| \star \,| \star \\ x_1 x_3^2 & \longleftrightarrow \star \;| \;| \star \star \\ x_2^3 & \longleftrightarrow \,| \star \star \star | \\ x_2^2 x_3 & \longleftrightarrow \,| \star \star \,| \star \\ x_2 x_3^2 & \longleftrightarrow \,| \star \,| \star \star \\ x_3^3 & \longleftrightarrow \,| \;| \star \star \star \end{align} $$

You can see the $\binom{2 + 3}{2} = 10$ monomials of degree $3$ in $2 + 1 = 3$ variables.

Answer 2

Your question confusingly lets $n$ be one less than the number of variables, a trickery to make the resulting formula more pleasant. But I don't like this kind of fiddling, because it makes me forget just which shift was necessary to get a nice answer (one more or one less?). So put $m=n+1$.

The number you are looking for, the number of monomials of degree$~d$ in the power series $\prod_{i=1}^m(1+X_i+X_i^2+X_i^3+\cdots)=\prod_{i=1}^m\frac1{1-X_i}$, is equal to the coefficient of $X^d$ in the power series $(1-X)^{-m}$ (just substitute $X_i:=X$ for all$~i$), which coefficient is by the binomial formula $(-1)^d\binom{-m}d=\binom{d+m-1}d$. Now you can again replace $m$ by $n+1$ to obtain $\binom{d+n}d=C_{n+d}^n$.

This answer assumes that you know how to "negate the upper index" in a binomial coefficient. The formula, which is well worth learning by heart, is $$ \binom nk=(-1)^k\binom{k-n-1}k \qquad\text{or equivalently}\qquad \binom{-n}k=(-1)^k\binom{k+n-1}k. $$ The formula is very general, the only condition is that $k\in\Bbb N$ (and this is already assumed for the definition $\binom xk=\frac{x(x-1)\ldots(x-k+1)}{k!}$), but $n$ could be anything. As you can see the upper index is not purely negated, but a negative upper index is surely made non-negative. In fact the symmetry is around the interval of values $n$ for which $\binom nk=0$, namely $0\leq n<k$ (those binomial coefficients in column $k$ that stick out above Pascal's triangle, but not as far as into the negative row indexes); this symmetry is $n\mapsto k-1-n$.