全射の個数の証明とベル数

まずは，$n$ 人を区別のある（ちょうど）$k$ 個のグループに分ける場合の数を考えます。もちろん人間は区別します。つまり，今回は「区別するもの」を「区別するグループ」に分ける場合の数の問題です。

具体例として $n=10,\:k=3$ でやってみます。

上記の例題を一般化すると公式1が証明できます。

ただし，グループの数が $4$ つ以上の場合はベン図を描くことができないので，難易度が上がります。この場合は包除原理を用います。→包除原理の2通りの証明

最短で得点力を上げる！高校数学の問題集〈典型250問〉の問題151では，$k=4$ の場合の問題と2通りの解法を紹介しています。

$n$ 人を区別のないちょうど $k$ 個のグループに分ける方法の数をスターリング数といい，$S(n,k)$ などと書きます。→スターリング数の漸化式と3つの意味

全射の個数の公式を用いることで，スターリング数をシグマと二項係数で表すことができます！

定義により，「区別のない場合」のスターリング数は「区別のある場合」の全射の個数の公式を $k!$ で割ったものなので，

$S(n,k)=\dfrac{1}{k!}\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n$

となります。

$n$ 人を区別のない$k$ 個以下のグループに分ける方法の数をベル数といい，$B(n,k)$ などと書きます。

スターリング数の公式を用いることで，ベル数をシグマと二項係数で表すことができます！

定義により $B(n,k)=S(n,1)+S(n,2)+\cdots +S(n,k)$ なので，

$B(n,k)\\ =\displaystyle\sum_{j=1}^kS(n,j)\\ =\displaystyle\sum_{j=1}^k\dfrac{1}{j!}\sum_{i=1}^j(-1)^{j-i}{}_j\mathrm{C}_{i}i^n$

なお，3つの公式を覚える必要はありませんが，導出できるようになっておきましょう。$k\leq 3$ なら大学入試として適度な難易度です。