重複組み合わせの考え方

mathtrain.jp

例題1

青，赤，黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

重複組合せを考えるときは、仕切りを引く方法に置き換えるとわかりやすい。

○ ○ ○ ○ | |
○ ○ ○ | ○ |
○ ○ ○ | | ○ 
...
| | ○ ○ ○ ○

という風に、4つのボールと2つの仕切りを使って、仕切りで分けられた左側を青、真ん中を赤、右側を黒と考える。

この組み合わせの数は、「6個の?のうち、2つを選んで仕切りにする組み合わせの数」と同じ。

? ? ? ? ? ?
↓
? ? ? ? | |

これは で求まります。

一般化すると、K種類の玉をN個選ぶときの組み合わせの数は、仕切りの数は K-1 になるので、

になります。

例題2

青，赤，黒の三種類の玉がたくさんある。この中から5つ玉を選ぶときに得られる色のパターンのうち，どの色の玉も一つ以上選ぶものが何通りあるか求めよ。

3種類のどの色の玉も一つ以上選ぶ必要がある場合、先に玉を3個割り振っておきます。

その後、残った 5-3 = 2 個の玉を、重複組み合わせで解けば良いです。

# 残った2個の玉と、2個の仕切りを使って重複組み合わせを解く
○ ○ | |

つまり で求まります。

PythonでCombination

最後に、Pythonでの組み合わせの数（Combination）の求め方を書きます。

from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

ans = combinatin_formula(6, 2)
print(ans)
# 15

ans = combinatin_formula(4, 2)
print(ans)
# 6

切り捨て除算しているのは、返り値を整数にするためです。

数え上げ問題難しいです＞＜