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

442

本文

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

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

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

$n! = \sum_{i = 0}^{n} (- 1)^{n - i}_{n} 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 数 (箱を区別しない場合) について同様に考えても得られます：

$S (n, n) = \frac{1}{n!} \sum_{i = 0}^{n} (- 1)^{n - i}_{n} C_{i} i^{n} = 1$

[1]

[2]

[3]

投稿日：2021年3月6日

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

12162

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

コメントはありません。

読み込み中