Theorem 1   If $S$ is a finite set of variable symbols, then the number of monomials of degree $n$ constructed from these symbols is ${n + m - 1 \choose n}$ where $m$ is the cardinality of $S$

Proof. The proof proceeds by inducion on the cardinality of $S$ If $S$ has but one element, then there is but one monomial of degree $n$ namely the sole element of $S$ raised to the $n$ th power. Since ${n + 1 - 1 \choose n} = 1$ the conclusion holds when $m = 1$

Suppose, then, that the result holds whenver $m < M$ for some $M$ Let $S$ be a set with exactly $M$ elements and let $x$ be an element of $S$ A monomial of degree $n$ constructed from elements of $S$ can be expressed as the product of 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 ${k + M - 2 \choose k}$ Summing over the possible powers to which $x$ may be raised, the number of monomials of degree $n$ constructed from the elements of $S$ is as follows: $$ \sum_{k=0}^n {k + M - 2 \choose k} = {k + M - 1 \choose k} $$

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