組合せ combinationとは

組合せとはn個のものからm個のものを選ぶときの選び方(組合せ)です。選ぶ順番は関係ありません。

例えば「田中」さん、「鈴木」さん、「佐藤」さん、「高橋」さん、「伊藤」さんの5人から3人を選ぶような場合に「田中」さん、「鈴木」さん、「佐藤」さんという順番で選んでも「佐藤」さん、「田中」さん、「鈴木」さんという順番で選んでも選ばれたのは「田中」さん、「鈴木」さん、「佐藤」さんの3人で違いはありません。このような場合は同じ組合せと考えます。

このような考え方を「組合せ」combinationといいます。

↑目次

組合せのパターン数

それでは組合せのパターン数はどうなるでしょうか。選んだ後の順番も考慮にいれるのであれば順列でも見た通りn個の中からm個を選んで並べる並べ方は_nP_m = n! / (n - m)! でした。

順列ではm個を並べる並べ方が含まれているためm個を並べる並べ方で割れば並べ方をのぞいた組合せを求めることができます。

m個を並べる並べ方はm×(m-1)×(m-2)×…× 1 = m! になります。よって組合せのパターン数は n! / (n - m)! / n! = n! / { m! (n - m)! } になります。順列の場合には_nP_mと表しましたが、コンビネーションの場合n個のものからm個を選ぶ組合せのパターン数を_nC_mと表記します。

_nC_m = n! / { m! (n - m)! }

前述した「田中」さん、「鈴木」さん、「佐藤」さん、「高橋」さん、「伊藤」さんの5人から3人を選ぶような場合、順列は₅C₃=(5 × 4 × 3 × 2 × 1)/{(3 × 2 × 1)(2 × 1)}= 10 通りとなります。

↑目次

combinations関数を用いた実装例

組み合わせを求めるにはcombinations()を使います。「田中」さん、「鈴木」さん、「佐藤」さん、「高橋」さん、「伊藤」さんから3人を選びます。combinations()を用いて実装すると以下のようになります。

from itertools import combinations
for m in combinations(["田中","鈴木","佐藤","高橋","伊藤"],3):
    print(m)

実行結果

('田中', '鈴木', '佐藤')
('田中', '鈴木', '高橋')
('田中', '鈴木', '伊藤')
('田中', '佐藤', '高橋')
('田中', '佐藤', '伊藤')
('田中', '高橋', '伊藤')
('鈴木', '佐藤', '高橋')
('鈴木', '佐藤', '伊藤')
('鈴木', '高橋', '伊藤')
('佐藤', '高橋', '伊藤')

このようにcombinations関数を用いると、組合せをすべて洗い出すことができます。

↑目次

重複組合せ combinations_with_replacementとは

重複組合せは、単なる組合せではなく重複して選ぶことを許可するような形になります。例えば次のような問題です。

袋の中に金、銀、銅のくじがあります。ここから2回くじを引きます。1回引くごとに袋の中にくじを戻します。このき金、銀、銅の組合せのパターンは何通りあるでしょうか(引いた順番は考えません)。2回ともすべて銅の場合せあるかもしれませんし、2回ともすべて金のときもあるかもしれません。

ここで引いたものを袋に戻すことで選んだものを再度選ぶことができます(重複を許可している)。このような組合せを重複組合せといいます。

↑目次

重複組合せのパターン数

金、銀、銅のくじを引く場合、引かれたものはかならず金、銀、銅の3つに分かれます。くじを引いた時に結果を分けるときに仕切りを2つ用意すれば3つに分けることができます。この仕切りを'|'で表します。仕切りで区切られた一番左を金、左から2番目を銀、左から3番目を銅のくじをおく場所にします。引いたくじの〇で表します。このとき金を2回連続で引いた場合にはいかのように表すことができます。

〇〇 | |

金が1回、銅が1回でた場合には以下のように表せます。

〇 | | 〇

つまり重複組合せのパターン数は〇と|の並び方の数と一致します。これは4箇所の中から〇をおく2箇所を選ぶ選び方の組合せと一致します(〇を2箇所おく場所を決めれば残りは必ず|が1通りに決まる)。よって₄C₂ = 6通りになります。

これを一般化すると、異なるn種類の中からr回重複して選ぶ組合せは_n+r-1C_rになります。

↑目次

combinations_with_replacement関数を用いた実装例

重複組合せの場合、pythonではcombinations_with_replacementを用います。先ほどの金、銀、銅のくじを2回引く場合をpythonで実装すると以下のようになります。

from itertools import combinations_with_replacement
for m in combinations_with_replacement(('金','銀','銅'),2):
    print(m)

実行すると以下のように全てのパターンを表示してくれます。

実行結果

('金', '金')
('金', '銀')
('金', '銅')
('銀', '銀')
('銀', '銅')
('銅', '銅')

↑目次

まとめ

組合せや重複組合せは、問題の意味や背景を理解していないと応用が難しくなります。きちんと意味を理解した上で利用すると活用すべき場面が分かってくるとおもいます。確率の問題は難しいと思う人もいるかもしれませんが一度理解してしまえばそれほど難しくありません。じっくり考えて理解してもらえればと思います。

↑目次