玉と箱を区別するかしないかで場合の数の公式は四通りに分かれる

「4 個を 3 つに配る」という同じ日本語から、81、36、15、14、4 と、まるで違う答えが出ます。

食い違いの原因は 2 つだけ。玉を区別するかどうか、箱を区別するかどうか。この 2 つの掛け合わせで 4 通りに分かれます。

分かれ道は 2 つ

配る問題を読んだら、最初にこの 2 点を確かめます。

玉に名前があるか。人を配るなら区別あり、同じ色のボールなら区別なし。

箱に名前があるか。部屋番号や組の名前があれば区別あり、ただ「3 つのグループ」なら区別なし。

図の配り方そのものは変わっていません。名前を消すたびに、別々だった配り方がひとつに重なる。だから数が減っていきます。

4 通りの公式

玉が $n$ 個、箱が $k$ 個とします。空の箱を許す場合の式を並べます^[1]。

左上と左下は式が閉じた形で書けます。右側の 2 つは、小さい場合に数え上げるしかありません。

高校の問題で出るのは、ほとんどが左側です。右側は、書き出せる大きさで出題される。

例：4 個の玉を 3 つの箱へ

具体的な数で 4 通りを並べます。空の箱は許すとする。

玉も箱も区別するなら、玉 1 個につき箱が 3 通り。$3^4=81$ 通り。

玉だけ区別しないなら、各箱に入る個数の組を数えます。${}_{4+3-1}{\mathrm{C}}_4={}_6{\mathrm{C}}_4=15$ 通り^[5]。

箱だけ区別しないなら、4 個を 3 組以下に分ける分け方で 14 通り。どちらも区別しないなら、4 を 3 個以下の和に分けて 4 通りです。

同じ「4 個を 3 つに」でも、値が 81 から 1 まで開きます。読み分けを誤ると、まったく違う答えになる。

空なしの列はどう出すか

空を許さない場合は、それぞれ別の手が要ります。

玉も箱も区別するなら、包除原理で空室のある配り方を引きます。$3^4-3\times 2^4+3\times 1=36$ 通り。

玉だけ区別しないなら、先に各箱へ 1 個ずつ置き、残り 1 個を 3 箱のどれかへ。3 通りです。

箱だけ区別しないなら、36 を箱の並べ替え $3!$ で割って 6 通り。どちらも区別しないなら、4 を 3 個の自然数の和に分けて $2+1+1$ の 1 通り。

1 箱に 1 個までという条件

3 つ目の条件として、「1 箱に 1 個まで」が付くこともあります。玉が箱より多ければ 0 通り。

玉 3 個を箱 4 つに、1 箱 1 個までで入れる場合を見ます。

箱を区別しないと、どの箱に入れても同じ形になります。だから 1 通り。

条件が 3 種類、区別の仕方が 4 通りで、全部で 12 の場合に分かれます。この一覧は twelvefold way と呼ばれる^[1]。

箱を区別しない場合の中身

箱を区別せず空も許さない分け方の総数には、第 2 種スターリング数という名前が付いています^[2]。記号は $S(n,k)$。

$S(4,1)=1$、$S(4,2)=7$、$S(4,3)=6$、$S(4,4)=1$ です。3 組以下なら $1+7+6=14$ で、さきほどの値と合う。

4 組まで全部足した 15 はベル数と呼ばれます^[6]。組の数を問わない分け方の総数です。

例：割り算で出す

4 個の玉を 3 つの箱に、空なしで入れる方法。箱に番号があれば 36 通りでした。

番号を消すと、箱の並べ替え $3!=6$ 通りが重なります。$36÷6=6$ 通り。

$S(4,3)=6$ と一致しました。箱を区別しない値は、区別した値を $k!$ で割れば出ます。ただし空なしのときに限る。

なぜ空を許すと割れないのか

空を許す場合に同じ割り算をすると、答えが合いません。$81÷6=13.5$ で整数にすらならない。

空の箱が 2 つできると、その 2 つを入れ替えても見分けが付きません。重なる回数が $3!$ より少なくなる場合が混ざる。

重なる回数がそろっていないので、一律に割れない。ここが、割り算で片づく問題と片づかない問題の境目です。

例：問題文の読み分け

同じ設定でも、言い回しで分類が変わります。3 つ並べて比べます。

「4 人を 3 つの部屋に入れる。部屋に番号がある」なら、玉も箱も区別する場合。$3^4=81$ 通り。

「同じ品物 4 個を 3 人に配る」なら、玉を区別せず箱を区別する場合。${}_6{\mathrm{C}}_4=15$ 通り。

「4 人を 3 つのグループに分ける。グループに名前はない」なら、玉を区別し箱を区別しない場合。空なしなら 6 通り。

人は区別し、同じ品物は区別しない。部屋番号や名前があれば箱を区別する。この 2 本の物差しで、たいていの問題は分類できます。

例：おつりのない支払い

10 円硬貨だけを何枚か 3 人に配ります。全部で 4 枚あり、1 枚も受け取らない人がいてもよい。

硬貨は同じもの、人は区別します。玉を区別せず箱を区別する場合にあたる。

${}_6{\mathrm{C}}_4=15$ 通りです。各人が何枚受け取るかの組 $(a,b,c)$ で、$a+b+c=4$ を満たすものを数えた値と同じ。

表に戻して確かめる

問題を解いたあと、自分がどの区画にいたかを言葉で言えるか確かめます。

「玉は区別する、箱は区別しない、空は許さない」と口に出せれば、使う式は 1 つに決まる。逆に言えないなら、まだ問題文を読み切っていません。

数を減らして書き出す手も有効です。玉 3 個、箱 2 つなら、どの分類でも手で全部並べられる。

よくある誤り

配る問題は、公式の数が多くて覚えにくく見えます。ただ、分かれ道は玉と箱と空の 3 つだけ。ここを毎回口に出して確かめれば、式は自然に決まる。

参考文献

^[1] が 12 通りの一覧、^[2] と ^[4] が箱を区別しない場合の数え方、^[3] が玉と箱の形での整理、^[5] が同じ玉を配る数え方、^[6] が組の数を問わない総数です。