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

場合の数に関する3つの公式を紹介します。見た目は複雑ですが,1が理解できれば2,3は難しくありません。順番に解説します。

  1. 全射の個数の公式:
    nn 人を区別のある(ちょうど)kk 個のグループに分ける場合の数は,
    i=1k(1)kikCiin\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n

  2. スターリング数の公式:
    nn 人を区別のない(ちょうど)kk 個のグループに分ける場合の数(スターリング数)は,
    1k!i=1k(1)kikCiin\dfrac{1}{k!}\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n

  3. ベル数の公式:
    nn 人を区別のない kk 個以下のグループに分ける場合の数(ベル数)は,
    j=1k1j!i=1j(1)jijCiin\displaystyle\sum_{j=1}^k\dfrac{1}{j!}\sum_{i=1}^j(-1)^{j-i}{}_j\mathrm{C}_{i}i^n

全射の個数の例

まずは,nn 人を区別のある(ちょうど)kk 個のグループに分ける場合の数を考えます。もちろん人間は区別します。つまり,今回は「区別するもの」を「区別するグループ」に分ける場合の数の問題です。

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

例題

1010 人をチームA,チームK,チームBに分ける場合の数を求めよ。ただし,各チーム最低1人はメンバーが属するものとする。

全射の個数

解答

1: 1010 人を 33 チーム以下に分ける場合の数は,3103^{10} 通り。

2:そのうち,「チームAに誰も属さない」or「チームKに誰も属さない」or「チームBに誰も属さない」場合の数を除けばよい。

2についてはベン図を描けば分かりやすい,Aに誰も属さない場合の数は 2102^{10} 通り,AA にも BB にも誰も属さない場合の数は 1101^{10} 通り,いずれも誰も属さない場合の数は 00 通りであることに注意する。よって,2の場合の数は,

32103110+03\cdot 2^{10}-3\cdot 1^{10}+0 と分かる。

よって,求める場合の数は,

3103210+3110=559803^{10}-3\cdot 2^{10}+3\cdot 1^{10}=55980 通り。

全射の個数の証明(一般の場合)

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

公式1:全射の個数の公式

nn 人を区別のある(ちょうど)kk 個のグループに分ける場合の数は,
i=1k(1)kikCiin\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n

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

証明

nn 人を kk チーム以下に分ける場合の数は knk^n 通り。

このうち,いずれかのチームに誰も属さないような場合の数を除けばよい。これは包除原理より,

k(k1)nkC2(k2)n++(1)kkCk11nk(k-1)^n-{}_k\mathrm{C}_{2}(k-2)^n+\cdots +(-1)^k{}_{k}\mathrm{C}_{k-1}1^n

となる。これを後ろから足し合わせる:

i=1k1(1)ki1kCkiin=i=1k1(1)ki1kCiin\displaystyle\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}\mathrm{C}_{k-i}i^n=\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}\mathrm{C}_{i}i^n

よって,求める場合の数は,

kni=1k1(1)ki1kCiin=i=1k(1)kikCiink^n-\displaystyle\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}\mathrm{C}_{i}i^n=\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n

→高校数学の問題集 ~最短で得点力を上げるために~のT120では,k=4k=4 の場合の問題と2通りの解法を紹介しています。

スターリング数を求める

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

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

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

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

となります。

ベル数を求める

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

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

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

B(n,k)=j=1kS(n,j)=j=1k1j!i=1j(1)jijCiinB(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つの公式を覚える必要はありませんが,導出できるようになっておきましょう。k3k\leq 3 なら大学入試として適度な難易度です。

区別するのかしないのか,きちんと区別しましょう。