重複組合せ

重複組合せはふつうの組合せに似ていますが、もとの集合 M の要素をくり返して使ってもよいところがちがいます。

定義と公式

わかりやすい例から始めましょう。お店に行って、遠足のために飲み物を12本買いたいとします。棚には、お茶、水、オレンジジュース、りんごジュースの4種類の飲み物があります。買い方はいろいろあります。たとえばお茶5本、水2本、オレンジジュース1本、りんごジュース4本と買うこともできますし、どの種類も3本ずつ買うこともできます。合わせて12本になる買い方は、全部で何通りあるでしょうか。

つまり、もとになる集合 M = {お茶, 水, オレンジ, りんご} があり、集合 M の要素から、重複を許して k 個（k = 12）を取る組合せが何通りあるかを考えます。

公式の導き方は、ほかの場合の数の問題より少し複雑です。まず、買い物を0と1の列として表します。1の個数がその種類の飲み物の本数を表し、0が種類の区切りになるようにします。（日本の教科書では、1の代わりに○、0の代わりに仕切り｜を使って ○○○｜○○○｜… のように表すことが多いですが、考え方は同じです。）たとえば 111011101111101 は、お茶を3本（最初の3つの1）、次に水を3本（0が区切りで、次の3つの1）、次にオレンジジュースを5本（0が区切りで、5つの1）、最後にりんごジュースを1本買ったことを表します。しくみ全体を次の図に示します。

$$\underset{\text{茶}}{\underbrace{111}}0\underset{\text{水}}{\underbrace{111}}0\underset{\text{オレンジ}}{\underbrace{11111}}0\underset{\text{りんご}}{\underbrace{1}}$$

お茶6本、水4本、りんごジュース2本を買い、オレンジジュースを買わないなら、列は次のようになります。

$$\underset{\text{茶}}{\underbrace{111111}}0\underset{\text{水}}{\underbrace{1111}}00\underset{\text{りんご}}{\underbrace{11}}$$

この列の長さは、いつも15になることに注目しましょう。全部で12本買うので、1は12個必要です。また、4つの種類を区切るために、区切りが3つ必要です。あとは、0を3つ含む長さ15の列が全部でいくつあるかを求めればよいのです。

0の位置だけを決めれば十分です。12個の1の間に3個の0を置けば、飲み物の買い方が1つ決まります。言いかえると、全部で15個のマスがあり、そのうち3個に0を入れます。残りのマスには自動的に1が入ります。

これは、ふつうの組合せの簡単な問題です。15個のマスに番号 {1, …, 15} をつけ、この集合から3つの数を選ぶと、0を入れる3つの位置が決まります。たとえば組合せ {2, 4, 7} なら、列 101011011111111 になります。2番目、4番目、7番目が0で、残りは1です。したがって、全部で

$${}_{15}{\mathrm{C}}_3=455$$

通りの0の置き方があり、4種類の飲み物から12本を買う買い方も455通りあります。

この考え方は一般化できます。要素の個数が n の集合 M から、重複を許して k 個を選ぶとき、長さ n + k − 1 の0と1の列（k 個の1と n − 1 個の0）をつくり、n − 1 個の0の置き方が何通りあるかを考えます。したがって、重複組合せの総数 {}_nH_k は次のようになります。

$${}_n{\mathrm{H}}_k={}_{n+k-1}{\mathrm{C}}_{n-1}={}_{n+k-1}{\mathrm{C}}_k.$$

最後の変形は、組合せの基本的な関係を使いました。

例題

1. 映画の試写会の招待券20枚を、10人のおばあさんに分ける方法は何通りあるでしょうか。1人のおばあさんが何枚でも、場合によっては全部の招待券をもらってもよいので、これは重複組合せの問題です。n と k がそれぞれ何かを正しく考える必要があります。招待券1枚ごとにもらう人を決めると考えれば、10人から重複を許して20人を選ぶ重複組合せです。言いかえると、長さ29で、20個の1と9個の0を含む列をつくります。したがって、n = 10, k = 20 で、答えは次のようになります。

$${}_{10}{\mathrm{H}}_{20}={}_{10+20-1}{\mathrm{C}}_{20}=\mathrm{10,015,005.}$$