組み合わせ

質問

(1)白の碁石が９個ある。これを、組を区別せずに、どの組も４個以下となるように３組に分ける方法は何通りあるか？また、A、B、Cの３人に、１人当たり４個以下になるように分ける方法は何通りあるか？
(2)９個の白の碁石をA、B、Cの３人に分ける。全員少なくとも１個はもらえるような分け方は何通りで、１つももらえない人がいてもよいとすると何通りになるか？
(3)赤球４個、青球４個、黄球１個と黒の碁石２個の合計１１個を１列に並べる。球が続けて５個以上現れない並べ方は○○×□□□通りある。

区別せず、や、区別して。少なくとも～
と聞かれると、何が何だかわからなくなってしまいます。
参考書を読んで、同じような問題の解法を見たのですが、いまいち解き方のコツがわかりません。
また、(3)のような問題は初めて見るので、ヒントがほしいのですが…

(1)～(3)の問題の解き方を教えて下さい。
私は組み合わせの問題が苦手なので、もしこの問題だったらこのパターン！
などのコツがあったら教えて下さい。
お願いします。

回答No.4

kumipapa · ベストアンサー

（１）の前半
実際の組み合わせを数えるのが早いでしょう。#1さんがおっしゃるように、
＞　４以下なので多いほうから数えるとよいでしょう。
＞　このとき、(a,b,c)は、a≧b≧c として数えましょう。
というのが、重複しないように組み合わせを数える場合の鉄則になります。すると、
（４，４，１）
（４，３，２）
（３，３，３）
の３通りしかありません。この問題の場合には、０個を含んだ分け方を考える必要はありませんが、例えば８個の白石を４個以下づつ３個の器に分けるというような場合には、（４，４，０）というような０個という分け方も数えるべきですから注意が必要。

（１）の後半
上で求めた３通りの分け方は、分けた組を区別しない場合ですから、この組をＡ，Ｂ，Ｃの３人にどのように割り振るかを考えれば良い。
（４，４，１）の時　３人のうち誰を１個にするかで、3Ｃ1 ＝ ３通り
（４，３，２）の時　４，３，２をA,B,Cの順に並べれば良いので３！＝６通り
（３，３，３）の時　３人とも同じ数だけ配るのは１通り
この合計で１０通りとなります。

（２）　１つももらえない人がいてもよい場合
説明の都合上、後半の「１つももらえない人がいてもよい場合」を先に求めます。
合計９個をＡ，Ｂ，Ｃに０個以上づつ分けるのですから、
「A,B,C≧０でA+B+C=9 となる整数解の組の数を求めよ」ということです。
やはり、#1さんの方法がこのような重複組み合わせの考え方の定番であり、どうしてもマスターしておく必要があります。
#1さんにちょっとだけ補足すると、○を９個ならべ、棒（｜）を２本立てて○を仕切り、その棒の立て方と、Ａ，Ｂ，Ｃの値とを次のように対応させて考えます。
○○｜○○○｜○○○○　⇒　Ａ＝２、Ｂ＝３、Ｃ＝４
○｜○○○○○○○｜○　⇒　Ａ＝１、Ｂ＝７、Ｃ＝１
｜○○○○○｜○○○○　⇒　Ａ＝０、Ｂ＝５、Ｃ＝４
｜○○○○○○○○○｜　⇒　Ａ＝０、Ｂ＝９、Ｃ＝０
○○○○｜｜○○○○○　⇒　Ａ＝４、Ｂ＝０、Ｃ＝５
このように｜で仕切られた○の数をＡ，Ｂ，Ｃの数に対応さえて考えることができ、○９個と｜２個の並べ方の数が、「A,B,C≧０でA+B+C=9 となる整数解の組の数」となることがわかります。
９個の○と２個の｜を並べる場合の数は、区別できない物の順列を計算して、１１！／（９！×２！）＝５５通りとしてもよいし、９＋２＝１１箇所から｜を置く２箇所を選ぶと考えて、11Ｃ2＝５５通りとしても良い。どちらでも同じです。

（２） 全員が少なくとも１個をもらう場合
「少なくとも～」の場合には余事象を考えるという手もありますが、この問題には適しません。「全員が少なくとも１個をもらう」の余事象は「少なくとも１人が０個」になりますので、問題がむしろ複雑になります。逆に「少なくとも１人が０個」という問題の場合に、その余事象を考えて「全員が１個以上（＝少なくとも１個）」とした方が、解法は容易になります。
この問題は、上と同じように９個の○を２個の｜で仕切る方法で考える事ができますが、
｜が右端　・・・・　Ａ＝０
｜と｜が並ぶ　・・　Ｂ＝０
｜が左端　・・・・　Ｃ＝０
が許されず、９個並べられた○と○の隙間（８箇所）のうち２箇所に１個づつ｜を立てることだけが許されます。結局、８箇所から｜を立てる２箇所を選ぶ場合の数を求めれば良いことになりますので、8Ｃ2＝２８通りが答えです。

これらの考え方をマスターしておくと、「少なくともｍ個づつ合計ｎ個を配る」にも対応可能になります。
⇒　A,B,C≧mでA+B+C=nの整数解の組み合わせの数
⇒　A,B,C≧0でA+B+C=n-3m の整数解の組み合わせの数と同じ
⇒　(n-3m)個の○と２個の｜（合計n-3m+2個）を並べる
⇒　(n-3m+2)Ｃ2
と求められます。（勿論、A,B,C≧1でA+B+C=n-3(m-1)と同じ、と考えて、n-3m+3個の○の隙間（n-3m+2箇所）のうち２箇所に｜を立てると考え、(n-3m+2)Ｃ2としてもよい）

（３）赤球４個、青球４個、黄球１個と黒の碁石２個を、球が５個以上連続しないように並べる

９個の球を並べておいて、それを碁石２個で仕切るという考え方をします。
９個の球を並べる場合の数と碁石で仕切る場合の数をかければ良いので、それが○○×□□□の○と□を埋めることになるのでしょう。

まず、９個の球を並べる場合の数は、９！／（４！４！）＝６３０通り。ですから、□□□が６３０なのでしょう。
次に、並べられた９個の球を２個の碁石で仕切る場合の数を求めますが、仕切られた組を左からＡ、Ｂ、Ｃとすると、球が５個以上連続しないということは、９個の球を４個以下づつＡ，Ｂ，Ｃに分けることになるので、その場合の数は既に（１）後半で求められており１０通り。
ですから、○○×□□□＝１０×６３０＝６３００です。

もし、１０通りというのが求められていなかった場合には、（２）の応用で１０通りというのを求めるのも手です。「A,B,Cに４個以下づつ配る」の余事象は、「Ａ，Ｂ，Ｃのいずれかは５個以上」です。さらに、Ａ，Ｂ，Ｃのうち一つを５個以上とすると他は４個以下となりますので、５個以上になるのはA,B,Cのうち一つだけ。こう考えて、求める場合の数を、「全体から余事象を引く」で求めてやると、

全体
A,B,C≧0でA+B+C=9の整数解の組の数　　⇒　11Ｃ2 = 55通り

余事象
Aに５個以上、B,Cには０個以上分ける場合の数を求め、Ａ，Ｂ，Ｃどれを５以上とするかが３通りだから、
（A≧5,B≧0,C≧0でA+B+C=9　の整数解の組の数）の３倍
⇒　（A,B,C≧0でA+B+C=4 の整数解の組の数）×３
⇒　6Ｃ2×３＝４５

よって、５５－４５＝１０通り

組み合わせの問題のパターンを列挙するのはなかなか大変です。間違える、分らないのは悪いことではありませんから、どこをどう間違ったかを検討し理解するのが大切でしょう。また、問題をよく読んで、自分が理解しやすいモデルに変形するのもアリです。ただし、答えが変わってしまうような変形は当然だめ。最後に、とにかく楽しむことです。

回答No.3

key-boy

♯2です
（２）の回答は間違えてました。
２１＋７」＝２８と
４５＋１０＝５５ですか？
すみません。

回答No.2

key-boy

＞(2)９個の白の碁石をA、B、Cの３人に分ける。全員少なくとも１個はもらえるような分け方は何通りで、１つももらえない人がいてもよいとすると何通りになるか？
♯１さんのやり方で
少なくとも１個は貰える場合は始めに１個ずつ渡しておく、残り６個を丸棒方式で（○と｜）両端を含め７箇所から２箇所を選ぶので
　　　　7Ｃ2＝２１通り
後者は　10Ｃ2＝４５通り

＞（3)赤球４個、青球４個、黄球１個と黒の碁石２個の合計１１個を１列に並べる。球が続けて５個以上現れない並べ方は○○×□□□通りある。

球だけ並べるのは９！/（４！・４！）
球が５個以上現れないとは２個の碁石の間が１～４個の場合
間が１個の時＝１通り、２個の時＝２通り、３個の時＝３通り、４個の時＝４通り、よって１＋２＋３＋４＝１０通り
９！/（４！・４！）×１０＝３６００通り
だと思うのですが、○○×□□□の意味が分かりません。

回答No.1

tarame

(1)の前半は、ただひたすら数える
４以下なので多いほうから数えるとよいでしょう。
このとき、(a,b,c)は、a≧b≧c として数えましょう。
(4,4,1),(4,3,2),(3,3,3)の３通りですね。
後半は、それぞれの組で、Ａ,Ｂ,Ｃの順に並べる方法を考えればよいわけですね。
(2)は、こんな風に考えるとよいでしょう。
　○○○○○○○○○　を２本の区切りで分けます。
例えば、○○｜○○○○｜○○○　は　Ａ２個Ｂ４個Ｃ３個
　　　　｜○○○○○｜○○○○　は　Ａ０個Ｂ５個Ｃ４個となります。
したがって、後半は　○９個と｜２個の順列の数になります。
　前半は、｜,｜が両端以外で隣り合わない場合の数になります。
(3)は、(1)の後半を(2)のように並べて、白玉に赤４つ、青４つ、黄１つを塗る場合の数を考えればよいですね。