1
大学数学基礎解説
文献あり

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

340
0
$$$$

本文

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

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

  • 単射の数は,$ {}_k \mathrm{P}_n $
  • 全射の数は,$ \displaystyle \sum_{i=0}^k \, (-1)^{k-i} {}_k {\mathrm C}_i \, i^n $

ここで全単射の数を考えると,上のそれぞれの式で $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 $

参考文献

投稿日:202136

この記事を高評価した人

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

この記事に送られたバッジ

バッジはありません。

投稿者

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

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中