How many monomial of degree $k$ in variable $X1,X2,・・・,Xn$?

Question

How many monomial of degree $k$ in variable $X1,X2,・・・,Xn$ ?

I heard this is $\binom{k+n+1}{k-1}$.

How can I deduce this?

I encountered this when I tried to calculate poincare series of $k[X1,・・・,Xn]$, where $k$ is actin ring.

Answer 1

The correct formula is $\binom{\mathrm{degree}+\mathrm{number~of~variables}-1}{\mathrm{number~of~variables}-1}=\binom{k+n-1}{n-1}$.

Someone in the comment linked to a smart proof. I'll show another, more pedestrian, approach.

Let's have $c_{k,n}:= \# \{(a_1,...,a_n)\in\mathbb{N}^n \,|\, a_1+...+a_n=k\}$.

We want to prove $$c_{k,n}=\binom{k+n-1}{n-1}$$

• A few simple cases : $c_{0,n}=1=\binom{0+n-1}{n-1}$ ; $c_{k,0}=0=\binom{k+0-1}{0-1}$ and $c_{k,1}=1=\binom{k+1-1}{1-1}$.

• Another useful relationship : $c_{k,n+1}= \sum_{j=0}^k c_{k-j,n}$. This is because $$\{(a_1,...,a_n,a_{n+1})\mathbb{N}^{n+1} \,|\, \sum_{j=1}^{n+1}a_j=k\}=\{(a_1,...,a_n,a_{n+1})\mathbb{N}^{n+1} \,|\, \sum_{j=1}^{n}a_j=k-a_{n+1}\}$$

Now $a_{n+1}$ can take any value between $0$ and $k$ (and only those), so we're done.

In particular $c_{k+1,n+1}= \sum_{j=0}^{k+1} c_{k+1-j,n}=c_{k+1,n}+\sum_{j=1}^{k+1}c_{k-(j-1),n}$. Therefore $$c_{k+1,n+1}=c_{k+1,n}+c_{k,n+1}$$

• Proceed by recursion on $n$.

The case where $n=0$ and $k$ is any integer has been dealt with in the first bullet.

Let $n_0\in\mathbb{N}$. Suppose for every $k\in\mathbb{N}$, $c_{k,n_0}=\binom{k+n_0-1}{n_0-1}$.

We want to show $c_{k,n_0+1}=\binom{k+n_0+1-1}{n_0+1-1}$ for any $k\in\mathbb{N}$.

Recursion on $k$. The formula is valid for $c_{0,n_0+1}$ (see 1st *).

Suppose the formula holds for $c_{k,n_0+1}$. Then

$$c_{k+1,n_0+1}=c_{k+1,n_0}+c_{k,n_0+1}=\binom{k+1+n_0-1}{n_0-1}+\binom{k+n_0+1-1}{n_0+1-1}$$

by recursion (on $n$ for the first, on $k$ for the second)

We're done thanks to Pascal's triangle : $\binom{k+1+n_0-1}{n_0-1}+\binom{k+n_0+1-1}{n_0+1-1}=\binom{k+1+n_0}{n_0}=\binom{k+1+n_0+1-1}{n_0+1-1}$