Cardinality of Set of Injections/Informal Proof

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be finite sets.


The number of injections from $S$ to $T$, where $\card S = m, \card T = n$ is often denoted ${}^m P_n$, and is:

${}^m P_n = \begin{cases} \dfrac {n!} {\paren {n - m}!} & : 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 - \paren {m - 1}$ 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:

$n \paren {n - 1} \paren {n - 2} \cdots \paren {n - m + 1} = \dfrac {n!} {\paren {n - m}!}$

$\blacksquare$


Sources