組分け問題全パターン

スポンサーリンク
組分けの問題は,\ 主に次の4条件で求め方が変わり,\ 非常にややこしい.   [1]\ \ 「モノが区別できるか否か}」}   [2]\ \ 「組が区別できるか否か}」}   [3]\ \ 「組の要素の個数が決まっているか否か}」}   [4]\ \ 「要素の個数が0個の組があってもよいか}」}  出題する意味があるのは以下の6パターンであり,\ 大筋では右のように求めることができる.  しかし,\ 必ずしも単純ではないので,\ 実際の問題で求め方を確認してほしい. モノの区別 & 組の区別 & 要素の個数 & & ○ & ○ & ○ & $組合せ$ & $C nr$ \\ ○ & × & ○ & $組合せ÷ 重複度$ & $C nr÷ p!$ \\ ○ & ○ & × & $重複順列$ & $n^r$ \\ ○ & × & × & $重複順列÷ 重複度$ & $n^r÷ p!$ \\ × & ○ & × & $重複組合せ$ & $\Kumiawase nr$ \\ × & × & × & $重複組合せ÷ 重複度$ & $\Kumiawase nr÷ p!{異なる}\,9個の玉を次のように分ける方法は何通りあるか.  (1)\ \ 3個ずつ3人に分ける.  (2)\ \ 4個,\ 3個,\ 2個の3組に分ける.  (3)\ \ 3個ずつ3組に分ける.  (4)\ \ 5個,\ 2個,\ 2個の3組に分ける. \\ 場合の数分野では,\ 特に断りがない限り,\ 人は区別できると考える. よって,\ (1)は「モノ(玉)の区別可」「組(人)の区別可」「要素の個数固定」}型である. 組分けの中で最も単純な型であり,\ A君,\ B君,\ C君に順番に3個ずつ分ける}と考えればよい.} まず,\ A}君には\dot{異}\dot{な}\dot{る}\,9個の玉から3個選んで分けるから C93=84\ (通り) \dot{異}\dot{な}\dot{る}\,n個のものの中からr個を選ぶときの組合せの総数が\,C nr\,なのであった. B}君には残りの6個の玉から3個選んで分けることになるから C63=20\ (通り) B君に分ける3個を選んだ時点で,\ C}君に分ける3個が自動的に決まる. つまり,\ C君への分け方は\,C33=1通りなので,\ 考慮してもしなくても同じである. (2)は3人ではなく単に3組に分けるなので,\ 「組の区別不可」型のように思える. しかし,\ 要素の個数が違えば組は区別できる}から,\ 実は(1)と同じ型である. 簡単のため,\ 異なる3個の玉を2個と1個の2つの組に分けるとしよう. 3個から2個選べば残りの1個は自動的に決まるから,\ C32=3通りの分け方がある. この3通りをすべて書き出してみると (①②,\ ③),\ \ (①③,\ ②),\ \ (②③,\ ①) このように,\ 要素の個数が異なる場合,\ 順番に選んでいけば組分けが一致する可能性はない.} これは,\ (1)と同じく,\ 組が区別できると考えてよいことを意味している. なお,\ 少ない個数の組になるものから選んだ方が計算が楽である. そこで,\ 解答ではまず9個から2個を選び,\ さらに残りの7個から3個選んでいる. 一方,\ (3)のように,\ 要素の個数が同じ組は区別できない.} よって,\ (3)は「モノ(玉)の区別可」「組の区別不可」「要素の個数固定」}型である. 簡単のため,\ 異なる6個の玉を2個ずつの3組に分けるとしよう. 順番に2個ずつ選んでいくと,\ C62×C42=15×6=90通りの分け方がある. この90通りの中には,\ 以下の6通りが含まれているはずである. この6通りは,\ A君,\ B君,\ C君に分ける(組が区別できる)場合には当然別物として数える.} しかし,\ 単に3組に分けるだけの組分けならば,\ どれも同じで1通りの扱いとなる. このように,\ 要素の個数が等しい組がある場合には重複が生じる}のである. 本問のように,\ 要素の個数が等しい組が3つある場合,\ その並べ方である3!=6通りが重複する. つまり,\ 組が区別できる場合とできない場合が常に3!:1=6:1で対応}する. 結局,\ 一旦組が区別できると考えて3個ずつ選び,\ 後で重複度3!\,で割ればよい.} (4)\ \ 以下のように,\ 2個の2組のみに重複度2!\,が生じる.} {異なる}\,6個の玉を次のように分ける方法は何通りあるか.  (1)\ \ 2人に分ける.\ ただし,\ 0個の人がいてもよい.  (2)\ \ 2人に分ける.\ ただし,\ 0個の人はいないものとする.  (3)\ \ 3人に分ける.\ ただし,\ 0個の人がいてもよい.  (4)\ \ 3人に分ける.\ ただし,\ 0個の人はいないものとする.  (5)\ \ 2組に分ける. ただし,\ 0個の組があってもよい.  (6)\ \ 2組に分ける. ただし,\ 0個の組はないものとする.  (7)\ \ 3組に分ける. ただし,\ 0個の組があってもよい.  (8)\ \ 3組に分ける. ただし,\ 0個の組はないものとする.\\ (1)\,~\,(4)は,\ 「モノの区別可」「組の区別可」「要素の個数不定」}型である. (5)\,~\,(8)は,\ 「モノの区別可」「組の区別不可」「要素の個数不定」}型である. 解答では数式のみ示したが,\ 記述試験ではなぜその式になるのかを日本語で説明しておくべきである. (1)\ \ 要素の個数が不定の場合,\ 1人1人にモノを対応させていくことができない. \ \ そこで,\ 逆に1つ1つのモノに人を対応させていく}ことを考える.\ 人数は固定されている. \ \ A,\ B}の2人に分ける場合,\ 1個の玉につきAかB}かの2通り}がある. \ \ 6個の玉があるから,\ 2・2・2・2・2・2=2^6\,通りとなる. \ \ これは,\ 以下のようにAとB}\,(計6個)の並べ方が何通りあるかを考えることに等しい. \ \ つまりは,\ 異なる2個(A,\ B})のものから重複を許して6個取って並べる重複順列}である. (2)\ \ 要素の個数が不定の場合,\ 0個の組が許されるか否かという観点からも出題される. \ \ 0個の組不可の場合は,\ 0個の組許可の場合(重複順列)から0個の組ができる場合を除く.} \ \ 本問の場合,\ 6個の玉すべてをAに分ける場合とBに分ける場合}の2通りを除く必要がある. (4)\ \ [1]\ ちょうど2人が0個の場合}\ と\ [2]\ 1人のみが0個の場合}\ を除く必要がある. \ \ [1]\ \ ちょうど2人が0個ということは,\ 6個の玉すべてを1人に分ける}ということである. \ \ \ \ \,6個の玉すべてをAに分ける場合とBに分ける場合とCに分ける場合}の3通りがある. \ \ [2]\ \ 1人のみが0個ということは,\ 6個の玉をちょうど2人に分ける}ということである. \ \ \ \ (2)より,\ 2^6-2}通りである. \ \ \ \ 2通りを除くのを忘れると,\ [1]と重複してしまうので注意してほしい. \ \ \ \ さらに,\ A,\ B,\ Cのどの2人に分けるかが3通り}ある(AとB,\ BとC,\ CとA)}. (5)\ \ 組が区別できない場合,\ 一旦組が区別できると考えて求めた後,\ その重複度で割る.} \ \ ここで,\ 以下のような2つの組分けは,\ A,\ B}の区別をなくすと同一の組分けになる. つまり,\ (1)の2^6\,通りの中には,\ AとB}の要素を入れ替えた組分けが2つずつペアで存在する.} \ \ よって,\ (1)の2^6\,を重複度2!\,で割る}だけで求まる.\ \ (6)も同様である. (8)\ \ (3)と(4)は(4)の方が面倒だったが,\ (7)と(8)は(7)の方が面倒なので,\ (8)を先に考える. \ \ 0個の組がない場合,\ 組が区別できる場合とできない場合が常に3!:1=6:1で対応する.} \ \ 以下のような6つの組分けは,\ A,\ B,\ C}の区別をなくすと同一の組分けになる. \ (7)\ \ (8)とは異なり,\ 安易に(3)を3!\,で割ってはならない.\ そもそも,\ 729÷6は割り切れない. \ \ 以下のように0個の組が2組ある場合のみ,\ 重複度が3!\,ではなく3になる.} \ \ 0個の2組は元々区別できないから,\ その並び換えの分の重複が生じていない}のである. \ \ 一方,\ 0個の組が1組だけならば,\ 重複度は0個の組がない場合と同様に3!\,となる. \ \ 結局,\ (3)の729通りのうちの3通りは3で割り,\ 残りの726通りを3!\,で割る}ことになる. \ \ 注意すべきは,「要素の個数固定」型と「要素の個数不定」型で重複度の基準が変わることである. \ \ 「要素の個数固定」型では,\ 「要素の個数が同じ組の数」が重複度の判断基準}となるのであった. \ \ 「要素の個数不定」型では,\ 「要素が0個の組の数」が重複度の判断基準}である. 「要素の個数不定」型には,\ 各組の要素の個数で場合分けする}という最終手段がある. 面倒だが,\ 「要素の個数固定」型となり\,C nr\,で求められるようになるので,\ わかりやすく確実である. 以下に要素の個数で場合分けする(7)の別解を示しておく.\ \ (7)以外も同様に求められる. (7)}\ \ ∴ 7つの場合は互いに排反}であるから 1+6+15+15+10+60+15=122\ (通り)} 区別できない}\ 6個の玉を次のように分ける方法は何通りあるか.  (1)\ \ 3人に分ける.\ ただし,\ 0個の人がいてもよい.  (2)\ \ 3人に分ける.\ ただし,\ 0個の人はいないものとする.  (3)\ \ 3組に分ける.\ ただし,\ 0個の組があってもよい.  (4)\ \ 3組に分ける.\ ただし,\ 0個の組はないものとする. \\ 6個の○と2本の|の順列の総数に等しい}から C82}=28\ (通り)}$   (2)\ \ $6個の○の間に2本の|を入れればよい}から C52}=10\ (通り)}$   3組とも同じ個数}になる分け方は $(2,\ 2,\ 2)$の1通り}. \ \ 2組が同じ個数}になる分け方(組を区別しない})は 3組が全て異なる個数}になる分け方(組を区別する})は $28-1-3・3}=18}\ (通り)$ 求める場合の数は 3組とも同じ個数}になる分け方は $(2,\ 2,\ 2)$の1通り}. \ \ 2組が同じ個数}になる分け方(組を区別しない})は $(1,\ 1,\ 4)$の1通り}. \ \ 3組が全て異なる個数}になる分け方(組を区別する}) (1)(2)は,\ 「モノの区別不可」「組の区別可」「要素の個数不定」}型である. (1)\ \ 本問は,\ x+y+z=6\ (x≧0,\ y≧0,\ z≧0)を満たす整数解の組数を求める}ことに等しい. \ \ つまりは重複組合せ}である.\ \ ○と|の並びに対応}させて求めるとよいのであった. \ \  \rei\ \ ○|○○○|○○ ⇔ x=1,\ y=3,\ z=2 \ \ 6個の○と2本の|の並べ方に帰着するから,\ 8!}{6!2!}\ (同じものを含む順列})として求められる. \ \ □□□□□□□□\ (8ヶ所)のうちの2個の□に2本の|を入れると考えて,\ C82\,としてもよい. (2)\ \ x+y+z=6\ (x≧1,\ y≧1,\ z≧1)を満たす整数解の組数を求める}ことに等しい. \ \ これは,\ ○\land ○\land ○\land ○\land ○\land ○\ の5つの\land に2本の|を入れる}ことに等しいのであった. \ \ 各文字が0以上となるように変数変換}する方法も重要なのであった. \ \  X=x-1,\ Y=y-1,\ Z=z-1とおくと X+Y+Z=3\ \ (X≧0,\ \ Y≧0,\ \ Z≧0) \ \  3個の○と2本の|の並べ方に帰着するから,\ 5!}{3!2!}\ または\ C52\,となる.  \rei\ \ ○○||○ (3)(4)は,\ 「モノの区別不可」「組の区別不可」「要素の個数不定」}型である.  この型は,\ 玉の個数が少なければしらみつぶしした方が早い.} このとき,\ x≧ y≧ z\ または\ x≦ y≦ z\ を満たすように書き出していくと重複を防げる. (3)\ \ 一般化可能な解法を別解として示しておいたので,\ 上級者は確認しておいてほしい. \ \ 組が区別できる場合の(1)の28通りを重複度で割る}ものである. \ \ この型では,\ 「要素の個数が同じ組の数」が重複度の判断基準}となる. \ \ ただし,\ 以下のように分け方によって重複度が変わる.} \ \ [1]\ \ 3組の要素の個数が等しいとき,\ 組を区別する場合としない場合は1:1で対応}する. \ \    \rei\ \ (A,\ B,\ C)}=(○○,\ ○○,\ ○○) \ \ [2]\ \ 2組の要素の個数が等しいとき,\ 組を区別する場合としない場合は3:1で対応}する. \ \ [3]\ \ 要素の個数が異なるとき,\ 組を区別する場合としない場合は3!:1=6:1で対応}する. \ \ 重複度が変わるため,\ まず28通りの中に以上の各場合が何通りずつあるかを考える必要がある. \ \ [1],\ [2],\ [3]\,のうち,\ [1]と[2]の場合は\dot{直}\dot{接}\dot{的}に求めることができる. \ \ [1]\ \ 玉の総数が3の倍数の場合は1通り,\ 3の倍数でない場合には0通り}である. \ \ [2]\ \ 先に組を区別しない分け方(△,\ △,\ △\ or}\ □)が何通りあるか}を考える. \ \ \ \ 玉の総数が2n\ (偶数)個}ならば,\ 次のようにn+1通り}ある. \ \ \ \  (0,\ 0,\ 2n),\ (1,\ 1,\ 2n-2),\ (2,\ 2,\ 2n-4),\ ・・・,\ (n,\ n,\ 0) \ \ \ \ 玉の総数が2n-1\ (奇数)個}ならば,\ 次のようにn通り}ある. \ \ \ \  (0,\ 0,\ 2n-1),\ (1,\ 1,\ 2n-3),\ (2,\ 2,\ 2n-5),\ ・・・,\ (n-1,\ n-1,\ 1) \ \ \ \   \rei\ \ 玉の総数が7個(n=4)のとき (0,\ 0,\ 7),\ (1,\ 1,\ 5),\ (2,\ 2,\ 3),\ (3,\ 3,\ 1) \ \ \ \ ただし,\ 玉の総数が3の倍数のときはこの中に[1]の1通りが含まれるので,\ これを除く.} \ \ \ \ (区別する):(区別しない)=3:1で対応するから,\ 3倍すると組を区別する分け方が求まる. \ \ 後は,\ 総数の28通りから[1]と[2]の場合を除くと,\ [3]の組を区別する分け方が求められる. \ \ これを3!\,で割ると[3]の組を区別しない分け方も求まり,\ 最後に[1]\,~\,[3]の場合を足し合わせる. \ \ [1]は玉の総数が3の倍数か否か,\ [2]は玉の総数が2の倍数か否かに依存する. \ \ よって,\ 一般化する場合には玉の総数mを以下の4パターンに分けて考える必要がある. \ \  lll} (.25zw}I}.25zw}) & 2の倍数\ かつ\ 3の倍数 & (m=6k) (.15zw}II}.15zw}) & 2の倍数\ かつ\ 3の倍数でない & (m=6k+2,\ 6k+4) (III}) & 2の倍数でない\ かつ\ 3の倍数 & (m=6k+3) (\scalebox{.9}[1]{IV) & 2の倍数でない\ かつ\ 3の倍数でない & (m=6k+1,\ 6k+5)