Number of injections

Builds on Cardinality of a finite set Falling factorial

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.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`0X0N833FF8`
URI	`m2://0X0N833FF8`
Kind	statement, theorem
Writing	W0 stub
MSC	05A05
Status	This copy of the site has no build data. Run `m2 status 0X0N833FF8`.
Uses	Cardinality of a finite set, Falling factorial

Number of injections

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here