部分順列の公式(定理)

第1段階(位置の設定):埋めるべき $k$ 個の位置に、順に位置1から位置 $k$ まで名前を付ける。すでに置いた対象を再利用せずに、$n$ 個の対象のいずれかで各位置を埋めることは、$k$ 個の連続する手順から成る作業である。

第2段階(乗法の法則を適用する):位置1は $n$ 通りで埋められる。埋めた後は対象が1つ使われているので、位置2は位置1で何が選ばれたかに関係なく $n-1$ 通りで埋められる。これを続けると、位置 $k$ はすでに $k-1$ 個の対象が使われているので $n-k+1$ 通りとなる。乗法の法則により、総数は積 $n(n-1)\cdots(n-k+1)$ である。

第3段階(階乗の商として書き直す):欠けている末尾 $(n-k)!$ を掛けてから割ると $n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}$ となり、これはまさに $A_n^k = \frac{n!}{(n-k)!}$ である。

第4段階(特別な場合 $k=n$):$k=n$ を代入すると、$0! = 1$ を用いて $A_n^n = \frac{n!}{0!} = \frac{n!}{1} = n!$ となり、順列の数 $P_n = n!$ が復元される。