# 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 $\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 one
element, then there is but one monomial of degree $n$, namely the sole element
of $S$ raised to the $n$-th power. Since $\left(\genfrac{}{}{0pt}{}{n+1-1}{n}\right)=1$, the
conclusion^{} holds when $m=1$.

Suppose, then, that the result holds whenver $$ 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 $\left(\genfrac{}{}{0pt}{}{k+M-2}{k}\right)$.
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}\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 monomials
of degree $n$ constructed from these symbols equals the cardinality of $S$.

Title | cardinality of monomials |
---|---|

Canonical name | CardinalityOfMonomials |

Date of creation | 2013-03-22 16:34:42 |

Last modified on | 2013-03-22 16:34:42 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 10 |

Author | rspuzio (6075) |

Entry type | Theorem^{} |

Classification | msc 12-00 |