1. 高校数学の美しい物語
  2. 全射の個数の証明とベル数

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

更新日時 2021/03/07

nn 人を区別のある(ちょうど)kk 個のチームに分ける場合の数は,

i=1k(1)kikCiin\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_k\mathrm{C}_{i}i^n

k=2,3k=2,\:3 の問題は大学入試として適度な難易度です。覚える必要はありませんが,導出できるようになっておきましょう。

目次
  • 全射の個数の例

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

  • スターリング数を求める

  • ベル数を求める

全射の個数の例

もちろん人間は区別します。つまり,今回は「区別するもの」を「区別するグループ」に分ける場合の数の問題です。

まず,具体例として n=10n=10 , k=3\: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 通り。

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

上記の議論を一般化すると冒頭の公式が証明できます。ただし,チームの数が 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

スターリング数を求める

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

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

人気記事
  1. 高校数学の美しい物語
  2. 全射の個数の証明とベル数