cardinality of monomials

Theorem 1.

If $S$ is a finite set of variable symbols, then the number of monomials ofdegree $n$ constructed from these symbols is $\mathrm{\left(}\genfrac{}{}{0pt}{}{n\mathrm{+}m\mathrm{-}\mathrm{1}}{n}\mathrm{\right)}$, where$m$ is the cardinality of $S$.

Proof.

The proof proceeds by inducion on the cardinality of $S$. If $S$ has but oneelement, then there is but one monomial of degree $n$, namely the sole elementof $S$ raised to the $n$-th power. Since $\left(\genfrac{}{}{0pt}{}{n+1-1}{n}\right)=1$, theconclusion holds when $m=1$.

Suppose, then, that the result holds whenver for some $M$. Let $S$ bea set with exactly $M$ elements and let $x$ be an element of $S$. A monomialof degree $n$ constructed from elements of $S$ can be expressed as the productof a power of $x$ and a monomial constructed from the elements of $S\setminus \{x\}$. By the induction hypothesis, the number of monomials of degree $k$constructed from elements of $S\setminus \{x\}$ is $\left(\genfrac{}{}{0pt}{}{k+M-2}{k}\right)$.Summing over the possible powers to which $x$ may be raised, the number ofmonomials of degree $n$ constructed from the elements of $S$ is as follows:

$$\sum _{k=0}^n\left(\genfrac{}{}{0pt}{}{k+M-2}{k}\right)=\left(\genfrac{}{}{0pt}{}{k+M-1}{k}\right)$$

∎

Theorem 2.

If $S$ is an infinite set of variable symbols, then the number of monomialsof degree $n$ constructed from these symbols equals the cardinality of $S$.