---
tag: 0X0N833FF8
kind: statement
role: theorem
name: Number of injections
msc: [05A05]
uses: [05099E1NMJ, 0N5M924N3P]
sources:
  - url: https://en.wikipedia.org/wiki/Falling_and_rising_factorials
    locator: Examples and combinatorial interpretation
---

## 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|0N5M924N3P]]
$$(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|0HGVCWQGY3]].
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|0CEBCS0E0E]].

## 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.