今回のテーマは重複組み合わせです!

 

場合の数の中でも難易度が高い重複組合せ

はじめに2つ質問です。

質問其の1:重複組合せは得意ですか?

質問其の2:nHrの記号を使わず問題を解いていますか?

・・・

・・・

両方ともYESだった人は問題ありません。さらっと流し読みして、記事の最後の実践問題だけは解いてみて下さい。

両方のうち1つでもNOが有ればこの記事がきっと役に立つと思います。

じっくり読み込んで得点源にしましょう!

重複組合せの公式:nHrは今すぐ忘れるべし!

場合の数と確率の分野には沢山の記号や公式がありますが、もしあなたがこの単元を得意にしたいなら、nCr(いわゆるコンビネーション)とn!(nの階乗)の2つ以外は基本的に使わないで下さい。

特にnHrなどの場合の数・確率の公式は簡単な問題なら便利ですが、入試のことまで考えると逆効果です。

2つだけしか使わない事によって思考力や応用力が付くだけでなく、この問題はCを使うのか?Hを使うのか、、、と混乱せずに済みます。

では本題に入ります。

今回の「重複組合せ」は基本的に「区別できないものを区別できるものに分ける」という問題であり、

その解き方は『○と|を使うたった1つの解法に帰着します。

??となっている人も居るかと思うので、例題を見ながら解法を習得して行きましょう。

重複組合せの解法(例題1)

(1)7個の(区別が付かない)ボールを3人に配る方法は何通りあるか。但し、一個も配られない人がいても良い。

 

(2)7個の(区別が付かない)ボールを3人に配る方法は何通りあるか。但し、全員最低一個は貰えるものとする。

※:コメント欄にて、ご質問をいただいた『(10個の玉(5個が赤・3個が青・2個が黄色)←区別がつく)を6人に配る(貰わない人がいても良い)』と言う応用問題の解説を行っています。合わせてご覧ください。

非常によく出るタイプの問題なので、一度は目にした事があるかもしれません。

“一人に重複して配っても良い”から重複組合せの問題と呼ばれているのですが、先述した様にnHrは使いません! 代わりに丸と仕切りを使った解法を紹介します。

丸仕切り法とは

(頻繁に出て来るのでこのサイトでは丸仕切り法と呼ぶ事にします:当然勝手に名付けたので、答案用紙に書かないでください( ̄∇ ̄))

丸仕切り法とは、配るものを丸:○で表して、○と仕切り|を置いて行く解法です。非常に応用が利くので必ず身につけて欲しいです

(この時注意が必要なのは、「丸の間に仕切りを置いて行く」のでは無く、「丸と仕切りを合計した数の部屋に◯と|を並べて行く」と考える事です。)

実際に使っていきましょう!

(例題1−1)典型的な「区別が付かないものを区別がつくものに分ける」問題

ちなみに「人」に関しては特別に何か注釈がついていない限り、「区別が付く」として扱うので注意して下さい。

丸仕切り法で、ボール7個を○に対応させて並べます。 

○○○○○○○  これを3人で分け、かつ貰えない人がいても良いので、

◯7個と仕切り2個、合わせて9個を同数の部屋(9室)に並べる場合の数を考えます。

例えば、○○|○|○○○○ だと、(2つ、1つ、4つ)配った事になります。従って、\({}_9C_2=36通り\)が正解となります。

2番は全員最低一個もらえるという部分が違うので少しだけ先に細工をしておきます

丸仕切り法を使う前に、3人に一個づつあげてしまうのです。そうすれば、残った4つの◯と2つの仕切りを並べるという(1)のパターンに帰着します。

丸仕切り法より丸と仕切りを入れる場所が6カ所、仕切り2つを入れる場所を6つから選ぶので、\({}_6 C_2=15通り\)が正解となります。

丸仕切り法の応用編

(例題2)今整数の組(w、x、y、z)について、

(2−1)1≦w≦x≦y≦z≦7となる(w、x、y、z)の組は幾つあるか。

この問題が仮に1≦w<x<y<z≦7であれば

1、2、3、4、5、6、7から4つ数字を選ぶことで、簡単に解けてしまう:\({}_7C_4 =35通り\)のですが、

等号が入っているために、同じ数字が重なる場合を考慮しないといけなくなってしまいました。

「重なる」・・・またしても重複組合せですね!

という事はもうこの記事を読んでいるあなたなら解けるはずです。丸仕切り法を使います!

この時どちらを○、|、とみるかだけは間違えないで下さい。

(2-1)であれば、アルファベットの文字が丸の数に当たります。そして1〜7の数字が仕切りの数になります。

(この区別が最初のうちは付きにくいですが、もし分からなくなったら具体例で実験してみて下さい。「解法がわからないときは”実験”してみる」←参考記事です。何度も類題を解いていると徐々に判断出来るようになります。)

従って、6つの仕切りと4つの丸を並べるので、

$${}_ 10 C_4=210通り・・・(答)$$

重要な別解:無理やり組合せの問題に変形する

この問題がややこしくなった原因は等号が入っている事でした。それならば、等号を外してやれば普通の組み合わせ問題になります。

そこで、w‘=w、x’=x+1、y‘=y+2、 z’=z+3

とおくと上手く等号が外れ、1≦w‘<x’<y‘<z’≦10

を満たす(w‘、x’、y‘、z’)の組みを求めると

「1、2、3、4、5、6、7、8、9、10」の10個の数字から4つ数字を選べば良いから、

$${}_ 10 C_4=210通り$$と解く事も出来ます。

では、今日のまとめとして、実際の入試問題を解いてみましょう。(15分程度時間をとって解いてみてください)

(実践・応用問題)

サイコロをn個同時に投げるとき、出た目の数の和がn+3になる確率を求めよ。   京大

(5分ほどで指針を決めて、思い付いたら10分で解答を作って行ってください。思い付かなければ、下の解説へ)

さて、今回も京大の過去問です。しかし、今回の記事を読んで理解出来ていれば、決して手が出ない問題では有りません!

 

<応用問題の解説と略解>

サイコロn個の目の数を各々X1、X2、・・・Xnとおきます。

今サイコロは1から6までのいずれかの目が出るので、X1〜Xnの整数の組みは全部で6^n個有ります。

問題文は以下の様に式で表せます。

X1+ X2+・・・+Xk+・・・+ Xn=n+3

(1≦Xk≦6 |k=1,2,・・・n)

ここで少しだけ頭を柔らかくして、今日学んだ内容を適用出来ないか考えてみます。

 

この式は、「n+3個のボールをn人に配り、そのn人が最低1個、最大6個貰える」と読み替えることができます。

(この辺りは少し経験がものを言います)

この読み替えさえ出来れば、最初に解いた例題1-2と同じように解く事ができます!

先に1個ずつボールを配って、残った{(n+3)-n}=3個のボールをn人で分けるとすると、丸仕切り法をつかって丸3個と仕切り(nー1)個を並べる事を考えて$${}_(n-1+3) C_3={}_(n+2) C_3・・・(1)$$

(1)より(n+2)(n+1)n/6 通り。$$\frac{(n+2)(n+1)n}{6}$$

\(全部で6^{n}通り\)あるから、n(n+1)(n+2)/6^(n+1)

$$\frac{n(n+1)(n+2)}{6^{n+1}}$$が答えとなります。

重複組み合わせのまとめと場合の数全般について

重複組合せの基礎の基礎から始めて、最後は京大の問題まで進みました。

内容が濃いので、全て一回で理解出来なくても大丈夫です。

何度も記事を読み返して、類題を解いてを繰り返しているうちにどんどん得意になっていきます。

特に場合の数と確率の分野は、難関大頻出な上、差がつきやすい分野なので、ここを攻略することが出来ればかなり大きなアドバンテージを得られます。

今後もこの分野の記事を書いていくので、是非このサイトと共に成績アップして貰えれば!と思います。

続編完成!>>「重複組み合わせの応用!等式を満たす整数の組を求める方法」<<

お役に立ちましたら、SNSでシェア、Twitterのフォローお願いします!

お疲れ様でした。

重複組み合わせに関連する場合の数と確率のまとめ記事はコチラ

いずれも、重要で知っていれば差がつくものを集めたので是非ご覧下さい!↓

場合の数と確率の解法一覧ページへ

コメント一覧
  1. 匿名 より:

    10個の玉を6人に分ける方法を教えてください。このとき1個ももらわない人がいても良いとします。お願いします。

    • Shu Yasuda より:

      ご質問ありがとうございます。

      ここでは「一つも貰わない人がいても良い」ので、10個の球(◯であらわします)を5つの棒(|であらわします)で仕切る、と言う風に考えることができます。

      これは、6人で分けるには間が6-1=5つ必要だからです。

      そして、◯◯◯◯◯◯◯◯◯◯|||||の計15個の並べ方を計算すれば問題の答えとなります。

      (例:|◯◯◯◯|◯||◯◯◯|◯◯ であれば、1人目が0個、2人目が4個、3人目が1個、4人目が0個、5人目が3個、6人目が2個もらえることになります。)

      ここで、15個の順列を求めますが、◯10個と|5個はそれぞれ同じもの=区別がつかないので、『同じものを並べる順列』より、15!/(10!×5!)=3003(通り)。

      以上が問題の答えと解説です。

  2. 匿名 より:

    返信ありがとうございます。丁寧な解法で理解できました。この問題について10個の玉に(赤5個、青3個、黄2個)という条件が付いた場合、これを6名に分ける場合はどうなりますか?すいませんがよろしくお願いします。

    • Shu Yasuda より:

      お役に立てて嬉しいです。球に区別がつく(赤、青、黄)と少々ややこしくなります。まず色別に分けて考えます。
      赤:5個を6人で分ける 丸が5つ、仕切りが五5つ(これは初めの問題と同じ解法です)10!/(5!×5!)=252
      青:3個を6人で分ける。丸が3つ仕切りが5つ。
      8!/(3!×5!)=56
      黄:同様に、丸が2つ仕切りが5つ。
      7!/(2!×5!)=21
      最後に、これらが独立である(『黄色の球の個数によって赤色の球の分け方が変わる』ようなことはありません)ことから、乗法定理を用いて252×56×21=296352・・・(答)
      かなり大きな数が出てきましたが、理解できましたでしょうか?

      • 匿名 より:

        なぜ色別に分ける必要があるのか教えていただきたいです。
        (15!/5!× 5!×3!×2!ではダメな理由を教えていただきたいです。)

        • Shu Yasuda より:

          コメントありがとうございます。(ただいま質問/コメントを沢山頂いており、返信が遅れることがあります。ご了承下さい)

          さて、15!/(5!5!3!2!)を計算すると、7567560(通り)となり、解答と一致しません。

          この式は、例えば15個の球(Aと書いてあるものが5つ、Bが5つ、Cが3つ、Dが2つ)の『同じものを並べる重複順列』の計算をしている事になります。

          この記事で扱っている解法は、球(=◯)を人数毎に仕切る(=|)事を応用することによって、それぞれの人が持つ球の数を求めるものです。

          従って、あくまでも同じものは(◯と|)の2種類のみなので、色毎に計算して掛け合わせています。(分母が5!5!3!2!だと球と仕切り以外の2つは何なのか分からなくなってしまいます。)

          まとめると、丸と仕切りだけで何個配る場合の数があるか知りたい→色の指定があるので一度に求められない→それぞれの色に分解して→最終的に掛け合わそう。と言う流れです

          この問題は割と複雑ですが、分母が2種類の階乗の掛け算である理由に立ち戻って考えると理解しやすいかと思います。

  3. 匿名 より:

    毎回丁寧に解答していただきありがとうございます。大変参考になりました。ありがとうございました。

    • Shu Yasuda より:

      こちらこそ良い質問を有難うございました。今後ともスマナビング!をご利用頂ければ幸いです。管理人より。

  4. 匿名 より:

    「0と書かれたカードが2枚、1と書かれたカードが3枚、2と書かれたカードが2枚ある場合、5枚のカードを選び並べて5桁の整数を作るとき、"5桁の偶数の整数"は何通りできるか」

    上記の問題について質問なのですが、上一桁は0が禁止で下一桁が1以外になる場合はどのように解いたらよろしいでしょうか?

    • Shu Yasuda より:

      ご質問ありがとうございます。現在質問が相次いでおり、時間の関係もある事から指針を提示する事に留めます。ご了承ください。

      これは『重複組み合わせ』に加えて「5桁の整数」しかも「偶数」と言う条件がついていて、かなり厄介な問題です。こう言った場合には、もう少し簡単な場合で実験し→そこから解法を見つける事(この問題では、【0,1,2,2の4つから3桁の偶数を作る場合の数】の様な問題で実験してみます)をオススメしています。

      そうすると、最も厳しい条件である0を選ぶかどうか(0の個数)で場合分けすれば良さそうです。

      本問に応用すれば、
      ・0を一個も選ばず1と2だけのケース、
      →(11122,11212,12112,21112)の4通り
      ・0ひとつのケース、
      ・0ふたつのケースに分けて
      それぞれで丸仕切り法を使ってみてください。ある程度書き出す必要がありますが、途中の手間を一部省略できます。

コメントを残す

関連キーワード

Twitterでフォローしよう