0

Let $s$ be the number of variables and $n$ be the degree of the monomials we want to count in $R[X_1,\dots,X_s]$. Then show, that the count is $$\delta(n,s):=\binom{s-1+n}{s-1}.$$

The question is a duplicate, but I have so far not been satisfied with any of the seen answers. Not here, not on google/lecture notes etc.. So here goes a proof using as little combinatorics as possible - the only proof with very little combinatorics involved I have seen here used that the substitution

$$R[[X_1,\dots,X_s]]\to R[[X]], X_i\mapsto X$$

is a well-defined homomorphism - something I have only seen as a statement in Zariski's "Commutative Algebra" Volume II...

So here goes my question + answer.

user26857
  • 52,094
polynomial_donut
  • 1,108
  • 5
  • 20

1 Answers1

1

The proof will be done by induction on the number $s$, and will in this way also make clear how the formula works out to be true.

Statement (using above definitions): $$\delta(n,s)=\binom{s-1+n}{s-1}$$

Note that for $s=1$ the statement is trivial. So assume that the statement holds for $s-1$, where $s>1$.
Also observe that we can obtain every monomial $X=X_1\cdot\,\dots\,\cdot X_s$ of degree $n$ by first choosing the degree $m_1$ of $X_1$ in $X$ from the set $\left\{1,\dots,n\right\}$, then the degree $m_2$ of $X_2$ from the set $\left\{1,\dots,n-m_1\right\}$, and so on, in such a way that $$ \sum_{i=2}^s m_i = n - m_1 $$ (w.l.o.g. assume $n>0$, because for $n=0$, there is nothing to show).

Thus, $$ \delta(n,s)=\sum_{m_1=0}^n \delta(n-m_1,s-1) \overset {(ind. hyp)} = \sum_{m_1=0}^n\binom{(s-1)-1+(n-m_1)}{(s-1)-1} = \sum_{m_1=0}^n\binom{(s-1)-1+m_1}{(s-1)-1} \overset{(*)}= \binom{s-1+n}{s-1}\quad ,$$ where $(*)$ comes from a general, inductively not hard to prove fact $$ \forall n,\sigma \in \mathbb{N}\left( \sum_{m=0}^n \binom{\sigma+m}{\sigma} = \binom{\sigma+1+n}{\sigma+1} \right) $$

polynomial_donut
  • 1,108
  • 5
  • 20
  • 1
    Excellent proof. The "stars and bars" argument is very useful because it is convincing. But this is a real proof. – student Sep 18 '19 at 01:32