## You are here

Homecardinality of monomials

## Primary tabs

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

## Mathematics Subject Classification

12-00*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella