組分け・重複組合せ（仕切り）
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
組分けで迷うのは、2つの軸を意識していないからである。分けられる側（人・ボール）に区別があるか、分ける先（組・箱）に区別があるか。この2つを最初に確定させれば、あとは機械的に処理できる。組にラベルがあるなら割らない、なければ同じ大きさの組の個数の階乗で割る。一方、重複組合せはこれとは別の問題で、区別しないものを区別する箱に入れる数え方であり、仕切りを使って順列に帰着させる。この2つを混同しないことが第一歩になる。
こんなときに使う
- 『A組・B組に分ける』→ 組に区別あり。割らない
- 『2つの組に分ける』（名前なし）→ 組に区別なし。同数の組の個数の階乗で割る
- 組の人数がすべて異なる → 入れ替わりようがないので割らない
- 『区別しないものを区別する箱に入れる』→ 重複組合せ（仕切り）
- 『x + y + z = n の非負整数解の個数』→ 重複組合せそのもの
手順
- 1. 分けられる側に区別があるか確認する
- 2. 分ける先（組・箱）に区別があるか確認する
- 3. 両方に区別あり → 順に選んでいく（積の法則）
- 4. 組に区別がない → 区別ありで数えてから、同じ大きさの組の個数の階乗で割る
- 5. 要素に区別がなく箱に区別あり → 仕切りを使う（重複組合せ）
- 6. 小さい場合で書き出して検算する
例題
6人を2人ずつ3つの組に分ける。(1) 組に A, B, C の名前がある場合 (2) 組に名前がない場合、それぞれ何通りか。
解答
- (1) 組に区別があるので、順に選んでいけばよい。
- A組に入る2人： C(6,2) = 15
- B組に入る2人： C(4,2) = 6
- C組に入る2人： C(2,2) = 1
- 15 × 6 × 1 = 90 通り
- (2) 組に名前がないので、3つの組を入れ替えたものは同じ分け方になる。
- 3つの組はすべて2人ずつで大きさが同じなので、入れ替え方は 3! = 6 通り。
- 90 / 3! = 90 / 6 = 15 通り
- 【注意：割ってよいのは大きさが同じ組どうしだけ】
- たとえば6人を1人・2人・3人に分ける場合、3つの組は大きさが違うので入れ替わりようがない。
- この場合は名前がなくても割ってはいけない： C(6,1)·C(5,2)·C(3,3) = 6·10·1 = 60 通り。
別解・ほかの見方
- 重複組合せ：区別しない n 個を区別する k 箱に入れる方法は C(n+k−1, k−1) 通り。○ を n 個と仕切り | を k−1 本並べる問題に読み替える
- x + y + z = 10 の非負整数解の個数は C(12, 2) = 66（○10個と仕切り2本の並べ方）
- 各箱に1個以上という条件があるときは、先に各箱に1個ずつ配ってから残りを配る
- 組分けを『各人がどの組に行くか』で数える方法（組に区別があるときのみ有効）
落とし穴
- 組に区別があるのに割ってしまう（最頻出）
- 大きさの異なる組まで含めて階乗で割ってしまう
- 重複組合せと組分けを混同する
- 『空の組を許すか』の条件を読み落とす
- 組に区別があるかで割り方が変わる点
なぜ大事か
整数解の個数、多項式の係数、確率の分母すべてに顔を出す
東大での出方
確率の分母、整数解の個数、多項式の係数など、いろいろな装いで現れる。東大では『区別があるかないか』を問題文から読み取らせる形で出るので、条件文の読解そのものが得点差になる。
確認問題
- 6人を1人・2人・3人の組に分ける方法は何通りか（組に名前はない）
- x + y + z = 8 を満たす非負整数の組は何通りあるか
- 区別しないボール10個を、区別する3つの箱に、各箱1個以上入れる方法は何通りか
発展
分けられる側にも分ける先にも区別がない場合（自然数の分割）は、高校範囲の公式では扱えない。この場合は書き出すか漸化式を立てるしかない、という限界を知っておくこと。
前提になるノード
このノードを前提にするノード
「場合の数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。