全単射の数から得られる階乗の公式

432

本文

有限集合から有限集合への写像について，単射の数および全射の数を考えます．
文献としては，次に挙げる写像12相 (twelvefold way) についての記事がわかりやすいと思います．

これらの文献にある事実から，写像における始域 (入力となる集合) のサイズを $n$，終域 (出力となる集合) のサイズを $k$ とするとき次が成り立ちます ($n$ 個の球を $k$ 個の箱に対応付けることと同じ)．

ここで全単射の数を考えると，上のそれぞれの式で $k=n$ とすればよいため，階乗に関する次の等式が得られます．

$ \displaystyle n! = \sum_{i=0}^n \, (-1)^{n-i} {}_n {\mathrm C}_i \, i^n $

検算

$n=4$ のとき，右辺は，
$ -4 + 6 \cdot 2^4 - 4 \cdot 3^4 + 4^4 \\ ~~ = -4+96-324+256 \\ ~~ =24=4! $

検算

$n=5$ のとき，右辺は，
$ 5 - 10 \cdot 2^5 + 10 \cdot 3^5 - 5 \cdot 4^5 + 5^5 \\ ~~ = 5-320+2430-5120+3125 \\ ~~ =120=5! $

なお上の等式は，第2種 Stirling 数 (箱を区別しない場合) について同様に考えても得られます：

$ \displaystyle S(n,n) = \frac{1}{n!} \sum_{i=0}^n \, (-1)^{n-i} {}_n {\mathrm C}_i \, i^n = 1 $

[1]

[2]

[3]

投稿日：2021年3月6日

高評価したユーザはいません

バッジはありません。

11038

Researcher and Developer for Algorithms, using C# (.NET). 数検1級金賞 (2002).

コメントはありません。

読み込み中