繰返し有りの組合せ数

Math Dude の「What Are Combinations? Part 2」から。

「順列と組合せ」は過去にも何度もやっているが、なぜか飽きない。新しい考え方に気づくのが面白いからかもしれない。特に Math Dude は、組合せの公式 _nC_r = _nP_r / r! を用いないで説明するのが良い。

Math Dude の過去の「Permutations 順列」と「Combination 組合せ」の投稿は以下

What Are Permutations?
What Are Combinations? Part1

これを踏まえての今回だが、末尾に「組合せの復習」を記した。

問題：袋に入っている3色3つの玉を、1つずつ抜き出し色を記録して袋に戻し、再度抜き出す、を繰り返す。色の組合せは何通りあるか？

単純な組合せとの違いは「同じ色の玉が繰返される」こと。

次のように考える。

　 | 　 | 　
　 　 　 | |
　 　 | 　 |

つまり、区切り線「 | 」の動きで、玉の組合せを変える。組合せを列挙すると以下のようになる（区切りの左の○は「赤」、中央は「緑」、右は「青」と考える）。

1. ○○○ | |
2. ○○ | ○ |
3. ○○ | | ○
4. ○ | ○○ |
5. ○ | | ○○
6. ○ | ○ | ○
7. | ○○○ |
8. | | ○○○
9. | ○ | ○○
10. | ○○ | ○

これを数式で考えると

　分母：○ と | の数は全部で 5 つ、この順列は 5!
　分子：3つの玉の順列 3!、区切り線の順列 2!

よって 5! / (3! × 2!) = 10
> factorial(5)/(factorial(3)*factorial(2))
[1] 10

これを一般式で表すと、組合せるものの数 m、区切り線の数 n

(m + n)! / (m! × n!)

6色6つの玉の場合を、この一般式で算出する

(6 + 5)! / (6! × 5!) = 11! / (6! × 5!) = 462
> factorial(11)/(factorial(6)*factorial(5))
[1] 462

462通りの組合せです。


組合せの復習

1 から 6 までの数字から3桁の数字の組合せの数を求める。

1 から 6 までの 3桁の数字の「順列」は 6 × 5 × 4 = 120、問題は「組合せ」なので「順列」から「ダブり」の数を取り除く必要がある。「ダブり」とは、選ばれた3桁の「順列の数」に相当する。つまり、3! = 3 × 2 × 1 = 6（言葉にすると「最初の桁に候補が3つ、次の桁では2つ、次は1つ」）。

よって順列は 120 / 6 = 20、つまり

選択肢から候補のものを取り出す「順列」の数

÷

選択された候補の「順列」の数

次の極端な例で考えてみる。

「1 から 6 までの数字から6桁の数字の組合せ」を同様の手順で解く。

1 から 6 までの 6桁の数字の「順列」は 6! = 720、選ばれた 6桁の「順列」は 6! = 720、よって 720/720 = 1、6桁から6桁の組合せは「1つ」なのは自明。