Cardinality of Set of Strictly Increasing Mappings

Theorem

Let $\left({S, \preceq}\right)$ and $\left({T, \preccurlyeq}\right)$ be tosets.

Let the cardinality of $S$ and $T$ be:

$\left|{S}\right| = m, \left|{T}\right| = n$

Then the number of strictly increasing mappings from $S$ to $T$ is $\displaystyle \binom n m = \dfrac {n!} {m! \ \left({n - m}\right)!}$.

$\displaystyle \binom n m$ is of course a binomial coefficient.

Proof

From Order Monomorphism iff Strictly Increasing and Strictly Monotone Mapping is Injective, a strictly increasing mapping $\phi$ from $S$ to $T$ is an order isomorphism from $S$ to $\phi \left({S}\right)$.

Let $\mathbb F$ be the set of all strictly increasing mappings from $S$ to $T$.

Let $\mathbb G$ be the set of all subsets of $T$ with $m$ elements.

By Unique Isomorphism between Finite Totally Ordered Sets, the mapping $\Phi: \mathbb F \to \mathbb G$ defined as:

$\forall \phi \in \mathbb F: \Phi: \phi \to \phi \left({S}\right)$

is a bijection.

The result follows from Cardinality of Set of Subsets.

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 19$: Theorem $19.11$