Cardinality of Set of Injections

Theorem

Let $S$ and $T$ be sets.

The number of injections from $S$ to $T$, where $\left|{S}\right| = m, \left|{T}\right| = n$ is often denoted $P_{nm}$, and is:

$ {}^m P_n = \begin{cases} \dfrac {n!} {\left({n - m}\right)!} & : m \le n \\ 0 & : m > n \end{cases}$

Informal Proof

This is the same question as determining how many permutations there are of $m$ objects out of $n$.

Informally, the thinking goes like this.

We pick the elements of $S$ in any arbitrary order, and assign them in turn to an element of $T$.

The first element of $S$ can be mapped to any element of $T$, so there are $n$ options for the first element.

The second element of $S$, once we've mapped the first, can be mapped to any of the remaining $n-1$ elements of $T$, so there are $n-1$ options for that one.

And so on, to the $m$th element of $S$, which has $n - \left({m-1}\right)$ possible elements in $T$ that it can be mapped to.

Each mapping is independent of the choices made for all the other mappings, so the total number of mappings from $S$ to $T$ is:

$\displaystyle n \left({n-1}\right) \left({n-2}\right) \ldots \left({n-m+1}\right) = \frac {n!} {\left({n - m}\right)!}$

$\blacksquare$

Formal Proof

Let $m > n$.

By the Pigeonhole Principle, there can be no injection from $S$ to $T$ when $\left|{S}\right| > \left|{T}\right|$.

Once $\left|{T}\right|$ elements of $S$ have been used up, there is no element of $T$ left for the remaining elements of $S$ to be mapped to such that they all still map to different elements of $T$.

Let $m = 0$.

The only injection from $\varnothing \to T$ is $\varnothing \times T$ which is $\varnothing$.

So if $m = 0$ there is $1 = n! / n!$ injection.

Let $0 < m \le n$.

As in the proof of Cardinality of Set of All Mappings, we can assume that $S = \N_m$ and $T = \N_n$.

For each $k \in \left[{1 \,.\,.\, n}\right]$, let $\mathbb H \left({k, n}\right)$ be the set of all injections from $\N_k$ to $\N_n$.

Proof by Principle of Finite Induction

Let:

$\displaystyle \mathbb S = \left\{{k \in \left[{1 \,.\,.\, n}\right]: \left|{\mathbb H \left({k, n}\right)}\right| = \frac {n!} {\left({n - k}\right)!}}\right\}$

Basis for the Induction

Let $k = 1$.

From Cardinality of Set of All Mappings, there are $n^1 = n$ different mappings from $S$ to $T$.

From Mapping from Singleton is Injection, each one of these $n$ mappings is an injection.

Thus:

$\displaystyle \left|{\mathbb H \left({1, n}\right)}\right| = n = \frac {n!} {\left({n - 1}\right)!}$

and so it follows that:

$1 \in \mathbb S$.

This is the basis for the induction.

Induction Hypothesis

We suppose that:

$\displaystyle \left|{\mathbb H \left({k, n}\right)}\right| = \frac {n!} {\left({n - k}\right)!}$.

This is the induction hypothesis.

We need to show that:

$\displaystyle \left|{\mathbb H \left({k+1, n}\right)}\right| = \frac {n!} {\left({n - \left({k+1}\right)}\right)!}$.

Induction Step

This is the induction step:

Let $k \in \mathbb S$ such that $k < n$.

Let $\rho: \mathbb H \left({k + 1, n}\right) \to \mathbb H \left({k, n}\right)$ be the mapping defined by:

$\forall f \in \mathbb H \left({k + 1, n}\right): \rho \left({f}\right) =$ the restriction of $f$ to $\N_k$

Given that $g \in \mathbb H \left({k, n}\right)$ and $a \in \N_n - g \left({\N_k}\right)$, let $g_a: \N_{k + 1} \to \N_n$ be the mapping defined as:

$g_a \left({x}\right) = \begin{cases} g \left({x}\right) & : x \in \N_k \\ a & : x = k \end{cases}$

Now $g$ is an injection as $g \in \mathbb H \left({k, n}\right)$, and as $g_a \left({a}\right) \notin g \left({\N_k}\right)$ it follows that $g_a$ is also an injection.

Hence $g_a \in \mathbb H \left({k + 1, n}\right)$.

It follows from the definition of $\rho$ that:

$\rho^{-1} \left({\left\{{g}\right\}}\right) = \left\{{g_a: a \in \N_n - g \left({\N_k}\right)}\right\}$

Since $g$ is an injection, $g \left({\N_k}\right)$ has $k$ elements.

Therefore $\N_n - g \left({\N_k}\right)$ has $n - k$ elements by Cardinality of Complement.

As $G: a \to g_a$ is clearly a bijection from $\N_n - g \left({\N_k}\right)$ onto $\rho^{-1} \left({\left\{{g}\right\}}\right)$, that set has $n - k$ elements.

Clearly:

$\left\{{\rho^{-1} \left({\left\{{g}\right\}}\right): g \in \mathbb H \left({k, n}\right)}\right\}$

is a partition of $\mathbb H \left({k + 1, n}\right)$, so by Number of Elements in Partition:

$\displaystyle \left|{\mathbb H \left({k + 1, n}\right)}\right| = \left({n - k}\right) \frac {n!} {\left({n - k}\right)!} = \frac {n!} {\left({\left({n - k}\right) - 1}\right)!}$

as $k \in \mathbb S$.

But $\left({n - k}\right) - 1 = n - \left({k + 1}\right)$.

So $k + 1 \in \mathbb S$.

By induction, $\mathbb S = \left[{1 \,.\,.\, n}\right]$ and in particular, $m \in \mathbb S$.

$\blacksquare$

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $3.1$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $5.5$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $4.4 \ \text{(ii)}$