# cardinality of monomials

###### 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 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$.

Title cardinality of monomials CardinalityOfMonomials 2013-03-22 16:34:42 2013-03-22 16:34:42 rspuzio (6075) rspuzio (6075) 10 rspuzio (6075) Theorem msc 12-00