Number of injections

Statement

Let $A$ and $B$ be finite sets with $|A| = k$ and $|B| = n$. Then the number of injective functions from $A$ to $B$ is the falling factorial $$(n)_k = n (n - 1) \cdots (n - k + 1).$$

Remarks

If $k > n$, then $(n)_k = 0$, and there is no injection. This is the pigeonhole principle. An injection from $\{1, \dots, k\}$ to $B$ is a $k$-permutation of $B$: an ordered list of $k$ distinct elements of $B$. For $k = n$ the count is $n!$, the number of permutations.

Explanations

L1 human

List the elements of $A$ and give each one an image in $B$ that is not used yet. The first has $n$ choices, the second $n - 1$, and so on, for $k$ steps.