How large is the permutation space for a block cipher with block size n, and why does this matter?

Question

Accepted Answer

For block size $n$, there are $(2^n)!$ possible permutations — the number of distinct bijections on the $2^n$ blocks. A $k$-bit key selects just $2^k$ of them, so the cipher must make those chosen permutations look random.
Three different counts — don't conflate them:

$2^n$ — the number of possible blocks (the inputs the cipher maps).
$(2^n)!$ — the number of possible permutations of those blocks: every bijection the cipher could conceivably be.
$2^k$ — the number of those permutations the $k$-bit key can actually select.

For AES ($n = k = 128$):

Possible permutations: $(2^{128})! \approx 10^{10^{39}}$
Permutations the key can select: $2^{128} \approx 3.4 	imes 10^{38}$

The key space is a vanishing sliver of the permutation space. The factorial does not add keys — it measures the ocean the $2^{128}$ selected permutations have to hide in. A good block cipher makes its $2^k$ selected permutations indistinguishable from one drawn at random from all $(2^n)!$.
Security implication: An attacker who doesn't know the key cannot determine which of the $(2^n)!$ permutations is being used. The cipher's security relies on the selected permutations appearing random to anyone without the key.