組み合わせ計算: 選び方の数を求めよう

組み合わせは、順番を気にせずに「何個選ぶか」を数える考え方です。

5人から2人を選ぶとき、Aさん→Bさん と Bさん→Aさん は同じ選び方として数えます。

使いどころ

• チームの選び方を数える
• 確率を計算する
• 全探索のパターン数を見積もる
• 動的計画法の問題で使う

手順

1. n 個から r 個を選ぶと考える
2. 上から n × (n-1) × ... とかける
3. 順番の重複を 1 × 2 × ... × r で割る

図で見る

コピペ用コード

def combination(n, r):
    if r > n - r:
        r = n - r
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    return result

print(combination(5, 2))

コードの読み方

• r = n - r にすることで、少ない回数で計算できます。
• result * (n - i) で選ぶ候補をかけます。
• // (i + 1) で、順番の重複を消しています。

注意点

とても大きな数を扱う場合や、余りを取りたい場合は、別の工夫が必要になります。