What is the factorial function and how is it relevant to cryptography?

Question

Accepted Answer

A block cipher is a bijection — a reversible lookup table that pairs every one of the $2^n$ block values with a distinct output. $(2^n)!$ counts how many such tables exist; the key selects one. The factorial measures the permutation space, which dwarfs the key space.

* Same $2^n$ values, a different pairing each time — each table is a distinct cipher. *
Why $2^n$ values but $(2^n)!$ ciphers (the point that trips people up):

$n$-bit blocks have $2^n$ possible values — that set is fixed; no rearrangement invents a value that is not already in it
A cipher does not pick a value; it picks the pairing — which input maps to which output, across the whole set at once. Because it must be reversible for decryption, that pairing is a bijection (one-to-one and onto)
The number of distinct pairings of $2^n$ values is $(2^n)!$ — that is how many different block ciphers are even conceivable on $n$-bit blocks
The key selects one table: a $k$-bit key reaches only $2^k$ of the $(2^n)!$ — the factorial counts permutations, not keys, so it never enlarges the key space
For AES ($n = 128$): there are $(2^{128})!$ conceivable tables, yet a 128-bit key still reaches only $2^{128}$ of them — a vanishing sliver that is nonetheless far too large to brute-force

Definition of the factorial:

$n! = n 	imes (n-1) 	imes (n-2) 	imes \dots 	imes 2 	imes 1$ — the number of ways to order $n$ distinct items
$0! = 1$ (by convention)
Example: $5! = 120$, $10! = 3{,}628{,}800$

Stirling's approximation for large $n$:
$$n! \approx \sqrt{2\pi n}\,\left(\frac{n}{e}ight)^n$$
For large $n$, computing $n!$ directly is impossible, but Stirling's formula gives a good approximation for the logarithmic (bit-length) calculations that matter in cryptography.
Go deeper:

Factorial (Wikipedia) — the function and Stirling's approximation for huge n.