数学A / 場合の数

組の大きさを指定しない組分け

★★★★ 難関組分け区別しない

問題

$6$ 人を $3$ つの組に分ける方法は何通りあるか。ただし、どの組にも少なくとも $1$ 人は入るものとし、組の人数は問わない。また、組は区別しないものとする。

ヒントを見る

組が区別できると考えて、各人を $3$ 組のどれかに入れる( $3^{6}$ )。ただし空の組があってはいけないので包除で除く。最後に組の区別をなくすため $3!$ で割る。

解答・解説

方針

まず $3$ つの区別する箱に、空の箱がないように分ける(全体 $3^{6}$ から、空箱ができる場合を包除で引く)。最後に組を区別しないので、区別した数を $3!$ で割る。

解答

⓪ 発想 — どう考え始めるか。 「組を区別しない」「人数は問わない」の $2$ つが厄介。まず「組を区別する」問題に直し、あとで区別をなくす。

$3$ つの区別する箱に $6$ 人を、空箱がないように入れる。全体 $3^{6}$ から、空箱ができる場合を包除原理で引く。 $3^{6} - (1 3) 2^{6} + (2 3) 1^{6} = 729 - 192 + 3 = 540$ 。

最後に組の区別をなくす。 $3$ つの組はどれも $1$ 人以上で人数が違えば区別が意味を持つが、区別しないので $3!$ で割る。 $540 \div 6 = 90$ 。

定理包除原理 —

3

組すべてに

1

人以上入る入れ方

= 3^{6} -_{3} C_{1} \cdot 2^{6} +_{3} C_{2} \cdot 1^{6}

① 区別する $3$ 組へ、空なしで入れる。 各人が $3$ 組のどれかに入る入れ方は $3^{6} = 729$ 。ここから「ある組が空」の場合を包除で除く。

$3^{6} -_{3} C_{1} \cdot 2^{6} +_{3} C_{2} \cdot 1^{6} = 729 - 3 \cdot 64 + 3 \cdot 1 = 729 - 192 + 3 = 540$

② 組の区別を消す。 いま組を区別して数えたが、実際は区別しない。組の並べ替え $3! = 6$ 通りが同じ分け方を重複して数えているので、 $6$ で割る。

$\frac{540}{6} = 90 通り$

まとめ:人数指定のない組分けは「区別あり(各人に組を割り当て)→ 包除で空組を除く → $3!$ で区別を消す」の $3$ 段。人数が同じとは限らないので $\frac{6 !}{2 ! 2 ! 2 ! 3 !}$ のような単純な式は使えず、包除が要る。この数は $6$ 人を $3$ つに分ける「第 $2$ 種スターリング数」 $S (6, 3) = 90$ にあたる。

発展 — 一歩先へ。 「 $n$ 人を $k$ 組(区別なし・各 $1$ 人以上)に分ける」数は第 $2$ 種スターリング数 $S (n, k)$ 。 $S (6, 3) = 90$ 。組を区別すれば $k! S (n, k)$ (全射の数)。 $k$ を $1$ から $n$ まで足した $\sum_{k} S (n, k)$ はベル数(組の数を問わない分割の総数)で、集合の分割を数える基本量だ。

答

$90$ 通り

別解

別解 — 人数の組(パターン)で場合分けする(苦手な人にも見通しのよいルート)。 $6$ 人を $3$ 組(区別なし・各 $1$ 人以上)に分けるとき、人数のパターンは $6 = 4 + 1 + 1 = 3 + 2 + 1 = 2 + 2 + 2$ の $3$ 通り。パターンごとに数える。

【 $4, 1, 1$ 】 $4$ 人組の選び方 $(4 6) = 15$ 。残り $2$ 人は $1$ 人ずつ( $1$ 通り、 $1$ 人組どうしは区別なし)。 $15$ 通り。

【 $3, 2, 1$ 】 $3$ 人 $(3 6) = 20$ 、 $2$ 人 $(2 3) = 3$ 、 $1$ 人 $1$ 。人数がすべて違うので区別の重複なし。 $20 \times 3 = 60$ 通り。

【 $2, 2, 2$ 】 $\frac{1}{3 !} (2 6) (2 4) (2 2) = \frac{15 \cdot 6 \cdot 1}{6} = 15$ 通り(同じ人数 $3$ 組は $3!$ で割る)。

合計 $15 + 60 + 15 = 90$ 。

包除 $+$ $3!$ で割る本解に対し、人数パターンで分けると各ケースが素朴な組合せになる。同じ人数の組がある( $2, 2, 2$ )ときだけ重複を割る、という注意が要点だ。

ポイント

区別する $3$ 組へ空なし: $3^{6} - 3 \cdot 2^{6} + 3 = 540$ (包除)。
組を区別しないので $\div 3!$ : $540/6 = 90$ 。

よくある間違い

組を区別しないのに $3!$ で割り忘れる(区別する箱への全射 $540$ を $3! = 6$ で割る)。
空箱を許してしまう(各組 $1$ 人以上=全射。 $3^{6}$ から空箱を包除で引く)。
人数パターン $2, 2, 2$ で同じ人数の組の重複( $3!$ )を割り忘れる(別解の場合)。