なかけんの数学ノート

【応用】重複組合せ

ここでは、同じものを何度選んでもよい「重複組合せ」を考えます。重複のある順列は【標準】重複順列で見ましたが、同じ重複でも「重複組合せ」はかなり難易度が上がります。

[広告]

最もシンプルな重複組合せ

まずは、重複組合せの中で、一番簡単な例を見てみましょう。

例題1
「A」「B」と書かれたカードが、それぞれ5枚ある。これらから5枚選ぶ方法は何通りあるか。

選ぶ方法なので、順番は関係ありません。「AABBA」と選ぶのと「BAABA」と選ぶのは、同じ選び方になります。

枚数の違いだけを考えればいいので、それぞれの枚数を書き出すと

 A:5, B:0
 A:4, B:1
 A:3, B:2
 A:2, B:3
 A:1, B:4
 A:0, B:5

の6通りだとわかります。この場合は、まだ簡単です。

カードが1枚増えるとどうなるか

続いて、カードが3枚のときを考えてみます。1枚増えただけで、かなりめんどくさくなります。

例題2
「A」「B」「C」と書かれたカードが、それぞれ5枚ある。これらから5枚選ぶ方法は何通りあるか。

枚数を考えてみます。Aが5枚のときは、BもCも0枚なので、1通りです。Aが4枚なら、Bが1枚かCが1枚の2通りです。Aが3枚のときは、Bが2枚・Bが1枚・Bが0枚の3通りです。

同じように考えていけば、Aが2枚のときは4通り、Aが1枚のときは5通り、Aが0枚のときは6通りとわかります。

これらを全部足して、\[ 1+2+3+4+5+6=21 \]通り、が答えとなります。

3枚ならまだこうした場合分けができますが、さらに1枚増えたらもう大変です。さすがに場合分けでは手に負えません。Aが〇枚で、Bが△枚のときは、□通り、というのを挙げていって全部足す、というのは時間がかかりすぎてしまいます。

重複組合せをもっと簡単に数えるには

3枚のカードを使った例題2について、もう少し考えてみましょう。

選び方なので、並び順は関係ありません。なので、選んだカードはアルファベット順に並べることにしましょう。具体的に書き出すと、次のような選び方があります。

 AABBB
 AABBC
 AABCC
 AACCC

これは、Aが2枚のときをすべて書き出したものです。AAが共通で、そこで区切られた後に、BとCの選び方が続きます。この区切りがよくわかるように、次のように書いてみます。

 AA|BBB|
 AA|BB|C
 AA|B|CC
 AA||CCC

「AA|BBB|」の最後の「|」は、「その後にCが0個続く=Cがない」を表しています。また、「AA||CCC」の中央の「||」は、「この間にBが0個ある=Bがない」を表している、ということです。

これ、今は「アルファベット順に並べる」と決めているので、こう考えてもいいんですね。

 〇〇|〇〇〇|
 〇〇|〇〇|〇
 〇〇|〇|〇〇
 〇〇||〇〇〇

はじめは「〇」として並び替えた後、左から順番に A, B, C を入れていく、という発想です。「|」を通過するたびに、文字を変えていく、と考えます。なので、最後の「〇〇||〇〇〇」ならはじめの2つの〇をAに変えて、Bがなくて、最後の3つをCに変えるということです。

なぜこんなことをしたかというと、こうすれば数えやすくなるんですね。これは「5つの〇と2つの | を並び替えたもの」と考えることができるわけです。並び替えて、左から順番に文字を入れていき、「|」を通過するたびに、文字を変えていけば、A, B, C の選び方と対応するんです。例えば、次のように対応させることができます。

 「〇〇〇〇〇|| ⇔ AAAAA」
 「〇〇〇|〇〇| ⇔ AAABB」
 「〇|〇|〇〇〇 ⇔ ABCCC」
 「|〇〇|〇〇〇 ⇔ BBCCC」
 「||〇〇〇〇〇 ⇔ CCCCC」

右側の、ABCの並び順を考えるのは大変ですが、左側の「〇と|」の並び方なら簡単に数えることができます。【標準】同じものを含む順列で見たように、「7か所から | が入る2か所を選ぶ」方法なので、\[ {}_7 \mathrm{ C }_2 =21 \]通り、と数えられます。上の例題の答えと一致していますね。

この方法がいいのは、場合分けがまったくいらなくなる、という点です。「(はじめの状況で)選ぶものの個数」を〇の個数に対応させ、「選ぶ対象の種類引く1」を | の個数に対応させ、〇と|の並べ方を数えれば、一発で求められます。区切りなので、1引くことに注意しましょう

一般的な重複組合せ

最後に、さきほどの考え方を使って問題を考えみましょう。

例題3
「A」「B」「C」「D」と書かれたカードが、それぞれ5枚ある。これらから5枚選ぶ方法は何通りあるか。

5枚選ぶので、5つの〇を考えます。A, B, C, D と4種類あるので、区切り | は3つ考えます。カードの選び方は、この8つを並べる方法と対応するので\[ {}_8 \mathrm{ C }_3 =56 \]通り、となります。

式は簡単ですが、考え方は難しいですね。

一般的に書くと、次のようになります。

重複組合せ
n 種類のものから r 個とる重複組合せは、 r 個の「〇」と $(n-1)$ 個の「|」をあわせた $(n+r-1)$ 個のものを並び替える方法と対応するから、この重複組合せの総数は\[ {}_{n+r-1} \mathrm{ C }_r = \frac{(n+r-1)!}{r!(n-1)!} \]通りとなる。

なお、 n 種類のものから r 個とる重複組合せの総数を、 ${}_{n} \mathrm{ H }_r$ で表すこともあります。上のことと合わせると\[ {}_{n} \mathrm{ H }_r = {}_{n+r-1} \mathrm{ C }_r = \frac{(n+r-1)!}{r!(n-1)!} \]となります。

おわりに

ここでは、重複組合せの総数を考えました。選ぶものと区切りをつかって対応させることで簡単に計算できるようになります。ただ、その対応の考え方は難しいし、何も知らない状態で思いつくのは困難です。ぜひとも、ここでマスターしてきましょう。

[広告]
対象者: 数学A
分野: 場合の数と確率
トピック: 場合の数
レベル: 応用
キーワード: 場合の数
更新日:2017/03/02