1
全単射の数から得られる階乗の公式
407
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 $
参考文献
投稿日：2021年3月6日
この記事を高評価した人
この記事を高評価した人
高評価したユーザはいません
この記事に送られたバッジ
この記事に送られたバッジ
バッジはありません。
投稿者
投稿者
コメント
コメント
他の人のコメント
コメントはありません。
読み込み中...
読み込み中