Let $X$ be a set of cardinality $n\in\N$.
A $k$-permutation of $X$ ($0\leq k\leq n$) is an injection from $\llbra k\rrbra$ to $X$.
A permutation of $X$ is a bijection from $\llbra n\rrbra$ onto $X$.
For any $n$, $k\in\N$ with $k\leq n$, we define
\[P(n,k) = \big\lvert\inj(\llbra k\rrbra,\llbra n\rrbra)\big\rvert\]as the number of $k$-permutations of $\llbra n\rrbra$. It can then be shown that this is the number of $k$-permutations of any set of cardinality $n$.
For any $n$, $k\in\N$ with $k\leq n$,
\[P(n,k) = \frac{n!}{(n-k)!}.\]
Proof.
- \[P(n,0) = \big\lvert\{\varnothing\}\big\rvert = 1 = \frac{n!}{(n-0)!}.\]
-
If $k\geq 1$: The function
\[\varphi : \inj(\llbra k\rrbra,\llbra n\rrbra)\to\inj(\llbra k-1\rrbra,\llbra n\rrbra), \, f\mapsto f\restriction_{\llbra k-1\rrbra}\]is surjective. It is easy to see that for every $g\in\inj(\llbra k-1\rrbra,\llbra n\rrbra)$,
\[\big\lvert\varphi^{-1}[\{g\}]\big\rvert = \big\lvert\llbra n\rrbra\setminus\ran g\big\rvert = n-k+1.\]By CV#PROP-FC-C,
\[P(n,k) = (n-k+1)\cdot P(n,k-1).\]Therefore,
\[P(n,k) = \left[\prod_{i=1}^k(n-k+i)\right]\cdot P(n-k,0) = \prod_{i=1}^k(n-k+i) = \frac{n!}{(n-k)!}.\]
As a corollary of PERM#PROP-F:
For any $n\in\N$,
\[\big\lvert\bij(\llbra n\rrbra,\llbra n\rrbra)\big\rvert = n!.\]