🏠 Home / 数学A / 場合の数と確率 / 組合せ

【応用】重複組合せ

🕒 2017/03/01 🔄 2023/05/01

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

📘 目次

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

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

例題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 を入れていく、という発想です。「|」を通過するたびに、文字を変えていく、と考えます。なので、最後の「〇〇||〇〇〇」ならはじめの２つの〇を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)!} \]となります。