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