2014/10/28

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

分野: 場合の数  レベル: 最難関大学

$n$ 人を区別のある(ちょうど)$k$ 個のチームに分ける場合の数は,
$\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_kC_{i}i^n$

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

全射の個数の例

もちろん人間は区別します。つまり,今回は「区別するもの」を「区別するグループ」に分ける場合の数の問題です。
まず,具体例として $n=10$, $\:k=3$ の場合をやってみます。

問題

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

全射の個数

解答

1:$10$ 人を $3$ チーム以下に分ける場合の数は,$3^{10}$ 通り。
2:そのうち,「チームAに誰も属さない」or「チームKに誰も属さない」or「チームBに誰も属さない」場合の数を除けばよい。
2についてはベン図を描けば分かりやすい,Aに誰も属さない場合の数は $2^{10}$ 通り,$A$ にも $B$ にも誰も属さない場合の数は $1^{10}$ 通り,いずれも誰も属さない場合の数は $0$ 通りであることに注意する。よって,2の場合の数は,
$3\cdot 2^{10}-3\cdot 1^{10}+0$ と分かる。
よって,求める場合の数は,
$3^{10}-3\cdot 2^{10}+3\cdot 1^{10}=55980$ 通り。

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

上記の議論を一般化すると冒頭の公式が証明できます。ただし,チームの数が $4$ つ以上の場合はベン図を描くことができないので,難易度が上がります。この場合は包除原理を用います。→包除原理の2通りの証明

証明

$n$ 人を $k$ チーム以下に分ける場合の数は $k^n$ 通り。
このうち,いずれかのチームに誰も属さないような場合の数を除けばよい。これは包除原理より,
$k(k-1)^n-{}_kC_{2}(k-2)^n+\cdots +(-1)^k{}_{k}C_{k-1}1^n$
となる。これを後ろから足し合わせる:
$\displaystyle\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}C_{k-i}i^n=\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}C_{i}i^n$
よって,求める場合の数は,
$k^n-\displaystyle\sum_{i=1}^{k-1}(-1)^{k-i-1}{}_{k}C_{i}i^n=\sum_{i=1}^k(-1)^{k-i}{}_kC_{i}i^n$

スターリング数を求める

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

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

定義により,「区別のない場合」のスターリング数は「区別のある場合」の全射の個数の公式を $k!$ で割ったものなので,
$S(n,k)=\dfrac{1}{k!}\displaystyle\sum_{i=1}^k(-1)^{k-i}{}_kC_{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}{}_jC_{i}i^n$

区別するのかしないのか,きちんと区別しましょう。
分野: 場合の数  レベル: 最難関大学