ThmDex – An index of mathematical definitions, results, and conjectures.
Result R1854 on D15: Set cardinality
Cardinality of the set of injections between finite sets
Formulation 0
Let $n, m \in \mathbb{N}$ each be a D996: Natural number such that
(i) $\text{Inj}(\{ 1, \ldots, n \} \to \{ 1, \ldots, m \})$ is the D2222: Set of injections from $\{ 1, \ldots, n \}$ to $\{ 1, \ldots, m \}$
Then
(1) \begin{equation} m > n \quad \implies \quad |\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})| = 0 \end{equation}
(2) \begin{equation} m \leq n \quad \implies \quad |\text{Inj}(\{ 1, \ldots, m \} \to \{ 1, \ldots, n \})| = \frac{n !}{(n - m) !} \end{equation}
Subresults
R4800: Number of injections from a finite set to itself
Proofs
Proof 3
Let $n, m \in \mathbb{N}$ each be a D996: Natural number such that
(i) $\text{Inj}(\{ 1, \ldots, n \} \to \{ 1, \ldots, m \})$ is the D2222: Set of injections from $\{ 1, \ldots, n \}$ to $\{ 1, \ldots, m \}$
Consider a sequence of $m$ empty boxes \begin{equation} \begin{split} f(1) & = \square \\ f(2) & = \square \\ f(3) & = \square \\ \quad & \enspace \vdots \\ f(m) & = \square \end{split} \end{equation} and the task of allocating the integers $1, \ldots, n$ to the boxes such that all boxes contain an integer, no box contains more than one integer, and that each integer is used only once. If we start allocating the numbers one by one, then for the first box we have $n$ integers to choose from. Having filled the first box, for the second box there are $n - 1$ choices to choose from. Continuing in this way, we find that there are \begin{equation} n (n - 1) (n - 2) \cdots (n - m + 1) = \frac{n!}{(n - m) !} \end{equation} distinct ways of filling the $m$ boxes with $n$ integers. Each allocation defines an injection, and each injection $\{ 1, \ldots, m \} \to \{ 1, \ldots, n \}$ corresponds to some such allocation, so we are done. $\square$