組分け問題全パターン

スポンサーリンク

組分けは単純な問題は教科書レベルの基本問題であるが、実際には「モノが区別できるか否か」「組が区別できるか否か」「組の要素の個数が決まっているか否か」「要素の個数が0個の組があってもよいか」で求め方が変わる。ランダムに出題されると非常に混乱しやすいので、扱い方をよく確認しておいてほしい。

なお、重複順列や重複組合せについては、実質同じ問題を各項目ですでに取り上げている。都合上解答は式だけの簡潔なものにとどめたが、記述試験では適度に自分の思考を説明しておくこと。

組分けの問題は,\ 主に次の4条件で求め方が変わり,\ 非常にややこしい.   「モノが区別できるか否か}」}   「組が区別できるか否か}」}   [3]「組の要素の個数が決まっているか否か}」}   [4]「要素の個数が0個の組があってもよいか}」}  大まかには次の6つの型に分類される.  しかし,\ 必ずしも単純ではないので,\ 実際の問題で確認してほしい. 組合せ$ $C nr}$ 組合せ 重複度$ 重複順列$重複順列 重複度{重複組合せ$すべて書き出すのみ }異なる9個の玉を次のように分ける方法は何通りあるか. 3個ずつ3人に分ける.  4個,\ 3個,\ 2個の3組に分ける.  3個ずつ3組に分ける.  5個,\ 2個,\ 2個の3組に分ける. 場合の数分野では,\ 断りがない限り,\ 人は区別できると考える. よって,\ は{「モノの区別可」「組の区別可」「要素の個数固定」}型である. これは,\ 組分けの中で最も基本的で単純な型である. A君,\ B君,\ C君に,\ 順に3個ずつ{選}{ん}{で}分ける}と考える.} まず,\ A}君に分ける3個の選び方は,\ 9個から3個選んで C93=84\ (通り) 84通りのいずれに対しても,\ B}君には残り6個から3個選ぶから C63=20\ (通り) 後は,\ {積の法則}を適用する. B君に分ける3個を選んだ時点で,\ C}君に分ける3個が自動的に決まる. つまり,\ C33=1通りなので,\ 考慮する必要はない. は一見すると,\ 「組の区別不可」型のように思える. しかし,\ 実は{要素の個数が違えば,\ 組は区別できる}から,\ と同じ型である. 例えば,\ 異なる3個の玉を2個と1個の2つの組に分けるとする. 3個から2個選べば残りの1個は自動的に決まるから,\ C32=3通りである. この3通りをすべて書き出してみると,\ 次のようになる. {要素の個数が異なる場合,\ 順に選んでいけば組分けが一致する可能性はない.} これは,\ と同じく,\ 組が区別できると考えてよいことを意味している. なお,\ 少ない個数の組を選んだ方が計算が楽である. よって,\ まず9個から2個を選び,\ さらに残りの7個から3個選んだ. 一方,\ のように,\ {要素の個数が同じ組は区別できない.} よって,\ は{「モノの区別可」「組の区別不可」「要素の個数固定」}型である. より簡単な例として,\ 異なる6個の玉を2個ずつ3組に分けるとする. 2個ずつ順に選んでいくとすると,\ この90通りの中には,\ 次の6通りが含まれるはずである. この6通りは,\ A君,\ B君,\ C君に分け与える場合は当然別物として数える.} しかし,\ 単に3組に分けるだけの組分けならば,\ どれも同じで1通りである. このように,\ {要素の個数が等しい組がある場合,\ 重複度が生じる}のである. 1組(a,\ b,\ c)に対して,\ その並び方である3!=6 の重複度が生じる. 具体的には,\ abc,\ acb,\ bac,\ bca,\ cab,\ cba\ である. 結局,\ {一旦組が区別できると考えて3個ずつ選び,\ 後で重複度3!で割ればよい.} は,\ {2個の2組のみに重複度2!が生じる}から,\ 2!で割って調整する. 異なる6個の玉を次のように分ける方法は何通りあるか.  2人に分ける.\ ただし,\ 0個の人がいてもよい.  2人に分ける.\ ただし,\ 0個の人はいないものとする.  3人に分ける.\ ただし,\ 0個の人がいてもよい.  3人に分ける.\ ただし,\ 0個の人はいないものとする.  2組に分ける. ただし,\ 0個の組があってもよい.  2組に分ける. ただし,\ 0個の組はないものとする.  3組に分ける. ただし,\ 0個の組があってもよい.  3組に分ける. ただし,\ 0個の組はないものとする. 「モノの区別可」「組の区別可」「要素の個数不定」}型である. ~は,\ {「モノの区別可」「組の区別不可」「要素の個数不定」}型である. モノが区別できて要素の個数が不定の場合,\ {重複順列}として考える. 重複順列の項目ですでに説明した通り,\ {6個の玉をすべて人に対応させればよい.} A,\ B}の2人に分ける場合,\ 1個の玉につきA,\ B}の2通りあるから,\ 2^6となる. また,\ これらの型は,\ {0個の組が許されるか否かで話が変わる}ので注意する. から,\ {0個の人ができる場合を引く.} つまり,\ 6個の玉すべてがAのみまたはB}のみに対応する2通りを除く. は,\ {0個の人が2人いる場合と1人いる場合を引く}必要がある. まず,\ 0個の人が2人いる場合は,\ {6個の玉すべてが1人に対応する}場合である. 6個の玉がすべてA,\ すべてB,\ すべてC}に対応する3通りがある. 0個の人が1人いる場合は,\ {6個の玉が2人に対応する}場合である. より,\ 2^6-2通りである.\ 1人のみに対応する2通りを引くのを忘れない. さらに,\ A,\ B,\ C}のどの2人に対応するかで3通りある(AとB,\ BとC,\ CとA)}. これらを3^6から引けばよく,\ 3^6-3(2^6-2)-3\ となる. {組が区別できない場合,\ 一旦区別できると考えて求めた後,\ 重複度で割る.} 6個を2人に分けることは,\ 重複を許してA,\ B}を6個並べる順列に等しい. ここで,\ 次のような2つの並びは,\ A,\ B}の区別をなくすと同じ組分けになる. を逆にした並びは,\ 区別をなくせば重複する.} よって,\ は,\ を{重複度2で割る}だけで求まる. はが厄介だったが,\ はが厄介なので,\ 先にを考える. {0個の組がない場合,\ 重複度は3!}であるから,\ を3!で割ればよい. 実際,\ 1つの組分けと並び方は,\ 次のように\ 1:3!=6で対応する は,\ 単純に3! で割ることはできない. 次のように{0個の組が2組あるとき,\ 重複度は3!ではなく3である.} {0個の組が2組あるとき,\ その2組は区別できない}のである. 一方,\ 0個の組が1組だけならば,\ 他の組と区別できる. よって,\ 0個の組が2組ある3通り以外は,\ すべて重複度が3!である. 結局,\ の729通りのうち,\ {726通りは3!で割り,\ 残りの3通りを3で割る.} {組の要素の個数で場合分けすると,\ 先の組合せの型に帰着する.} 面倒だが,\ より複雑な問題になると,\ この場合分けがわかりやすく確実である. 要素の個数で場合分けするの別解を示しておく.\ 以外も同様に求められる. 区別できない6個の玉を次のように分ける方法は何通りあるか.  3人に分ける.\ ただし,\ 0個の人がいてもよい.  3人に分ける.\ ただし,\ 0個の人はいないものとする.  3組に分ける.\ ただし,\ 0個の組があってもよい.  3組に分ける.\ ただし,\ 0個の組はないものとする. ○6個と|\ 2本の順列の総数に等しい}から C82}={28\ (通り)}$  $○6個の間に|\ 2本並べる順列の総数に等しい}から  は,\ {「モノの区別不可」「組の区別可」「要素の個数不定」}型である. これは,\ 実質的に{重複組合せ}の問題である. 3人から重複を許して6回選ぶと考えるわけだが,\ この考え方はわかりにくい. 重複組合せの基本的な考え方である{○と|の並び方をイメージすればよい.}  ○|○○○|○○ → A1個,\ B3個,\ C2個} 結局,\ {同じものを含む順列}に帰着する. 8箇所から2本の|の位置を選んでもよいし,\ \にするのも有効であった. 整数解の組数の問題として取り上げた重複組合せの応用問題と同じである. を満たす整数解の組数である. この問題の解法は3つあった. 1つは,\ {変数変換}により,\ 重複組合せに帰着させる.  X=x-1,\ Y=y-1,\ Z=z-1\ とおくと ここでは,\ 次の簡潔な方法を本解とした. {○\land ○\land ○\land ○\land ○\land ○の5箇所の\land に2本の|を入れる.} また,\ {○を先に1個ずつ配った後で,\ 残りの3個を分配する}方法もあった. 3個の○と2本の|の並び方であるから,\ C52通りとなる. は,\ {「モノの区別不可」「組の区別不可」「要素の個数不定」}型である.  この型は,\ {単純な計算方法が存在しない}ことを覚えておく. よって,\ 余計なことは考えず,\ さっさとすべての場合を書き出そう. このとき,\ x y z\ か\ x y z\ を基準に書き出すと,\ 重複を防げる.
タイトルとURLをコピーしました