順列と組合せ
Permutations and Combinations ・ じゅんれつとくみあわせ
起こりうる場合を漏れなく数え上げる技法。確率計算の腕力になる道具
✦ 30秒で試す — 航海並べ方を数えるか、選び方を数えるかで、答えは何倍も違う組合せで数えた手札の数は、順列の数の何分の1？予想してみる概要
順列と組合せは、「起こりうる場合が全部で何通りあるか」を漏れなく・重複なく数え上げるための技法です。順列（permutation）は「並べる順序を区別する数え方」、組合せ（combination）は「順序を区別せず選び方だけを数える数え方」を指し、あわせて「場合の数」の計算、より広くは組合せ論（combinatorics）と呼ばれる分野の入り口にあたります。
なぜこれが統計の星図に載っているかというと、確率の最も基本的な計算方法が「事象に含まれる場合の数 ÷ 全体の場合の数」だからです。「くじで当たりを2本引く確率」「7人から3人の当番を選ぶ選び方」— こうした問いに答えるには、分子と分母の場合の数を正確に数える腕力が要ります。順列と組合せは、その数え上げを人力の書き出しから式による計算に変える道具です。
数え上げというと地味に聞こえますが、場合の数はすぐに爆発します。52枚のトランプの並べ方は52の階乗、およそ10の68乗通り — 全部書き出す戦略は最初の数個で破綻します。「書き出さずに数える」技術は、確率計算だけでなく、パスワードの強度の見積もりやアルゴリズムの計算量の評価など、爆発する可能性の空間を相手にするあらゆる場面で使われています。
なぜ生まれたか
体系的な数え上げの需要を生んだのは賭博の問題です。17世紀初め、ガリレオは賭博好きの依頼を受けて「サイコロ3個の目の和が10になるのと9になるのとでは、どちらが起こりやすいか」という問いに答えました。和が9になる目の組み合わせも10になる組み合わせも6種類ずつあるので、同じに見えます。ところが目の出方を順序まで区別して数えると、和が10は27通り、9は25通り — 順序を無視した数え方では、等しく起こりやすくない「組」を同じ重みで数えてしまい、経験則と食い違うのです。続いて1654年、パスカルとフェルマーが確率を「場合の数の比」として計算する方法を確立したとき、正確な数え上げの技法は確率論の生命線になりました。
しかし場合の数は急激に大きくなるため、書き出しによる数え上げはすぐ限界を迎えます。そこで「順序を区別するなら掛け算で数えられる」「順序を区別しないなら並べ替えのぶんだけ割ればよい」という規則が整理され、階乗・順列・組合せの記法として定式化されました。パスカルが整理した「算術三角形」（パスカルの三角形）は、各段の数が組合せの数 nCr を並べたものになっていて、この計算を機械的に行うための当時の早見表でした。数え上げが式になったことで、確率は「原理的には計算できる」ものから「実際に計算できる」ものへと変わりました。
詳細
すべての土台 — 積の法則
数え上げの出発点は「積の法則」です。選択が段階に分かれていて、各段階の選び方が互いに影響しないなら、全体の場合の数は各段階の選択肢の数の掛け算になります。シャツ4着とズボン3本の組み合わせは 4 × 3 = 12通り。4桁の暗証番号は各桁10通りの4段階で 10 × 10 × 10 × 10 = 1万通り。順列も組合せも、突き詰めればこの掛け算の応用です。
順列 — 順序を区別して並べる
異なる n 個から r 個を取り出して一列に並べる並べ方が順列で、nPr と書きます。1番目は n 通り、2番目は残りの n−1 通り、と積の法則を r 段階適用して、nPr = n × (n−1) × … × (n−r+1) となります。7人から委員長・副委員長・書記を選ぶなら、役職という「順序」があるので 7P3 = 7 × 6 × 5 = 210通りです。n 個すべてを並べる特別な場合が階乗 n! で、7人の並び順なら 7! = 5040通りになります。
組合せ — 順序を無視して選ぶ
一方、7人から掃除当番を3人選ぶだけなら、選ばれた3人の中に順序はありません。順列 210通りの中では同じ3人組が並び順の違いで 3! = 6回ずつ重複して数えられているので、6で割った 35通りが答えです。これが組合せ nCr で、「順列を、順序の並べ替えのぶんで割る」という関係 nCr = nPr ÷ r! がそのまま定義になっています。
5人から3人を選んで一列に並べる並べ方が、この60枚のカードです（5P3 = 5×4×3 = 60）。どれか1枚をタップすると、同じメンバーでできたカードが光ります。
カード1枚 = 順番つきの並べ方（順列）。山1つ = 順番を無視した選び方（組合せ）
上の部品で「同じメンバーで揃える」を押すと、60枚のカードが 10組 × 6枚 の長方形に並び直ります。順列 = 組合せ × 並び替え（nPr = nCr × r!）という掛け算の関係が、そのまま面積として見えます。これを逆にたどって割り算にしたものが組合せの公式で、nCr = n! ÷ (r! × (n−r)!) と書くこともできます。選ぶ r 個と「選ばれなかった n−r 個」は1対1に対応するので、nCr = nC(n−r)（5人から3人を選ぶのは、残す2人を選ぶのと同じ10通り）という対称性もここから出てきます。
実務で迷ったときの判定基準はひとつだけです。「取り出した結果を入れ替えたら別物になるか？」— 役職・座席・暗証番号のように入れ替えが意味を持つなら順列、当番・くじの当たり・カードの手札のように入れ替えても同じなら組合せです。
確率計算への応用
順列と組合せが最も活躍するのは、確率の「場合の数の比」による計算です。たとえば「当たり4本を含む10本のくじから3本引いて、ちょうど当たり2本を引く確率」は、分母が 10C3 = 120通り、分子が「当たり4本から2本 × はずれ6本から1本」で 4C2 × 6C1 = 36通り、よって 36/120 = 0.3 と求まります。有名な誕生日のパラドックス（23人いれば誕生日の重複が5割超）も、「全員バラバラになる場合の数」を順列で数えて余事象を取るだけで確かめられます。直感では見当もつかない確率が、数え上げで機械的に出せるのです。
また、くじを続けて引くような問題は「1本目が当たりで、かつ2本目も当たり」という段階的な確率として条件付き確率の掛け算でも解けます。組合せで一気に数える方法と、条件付き確率で逐次掛ける方法が同じ答えに至ることを確かめると、両者の理解が一段深まります。さらに「コインを n 回投げて表がちょうど r 回出る確率」の場面では、n 回のうち表になる回を r 個選ぶ選び方 nCr がそのまま二項分布の係数になり、確率分布の世界へつながっていきます。nCr が「二項係数」とも呼ばれるのはこのためです。
同じものを何度も選べるとき
ここまでは「一度選んだものはもう選べない」前提でした。暗証番号のように同じ数字を何度使ってもよい並べ方は重複順列で、各桁が n 通りなので n^r 通り（4桁なら 10^4）。同じ種類を何個でも選べる選び方（3種類の果物から5個を詰め合わせる、など）は重複組合せで、「5個の玉と、種類を仕切る2本の仕切りの並べ方」に言い換えると 7C2 = 21 通りと数えられます。問題を見たら「順序を区別するか」「同じものを繰り返し選べるか」の2つを確かめ、4つの型のどれかに当てはめるのが定石です。
落とし穴 — 重複と「同様に確からしいか」
数え上げの典型的な失敗は2つあります。ひとつは同じ場合を二重に数えること・数え漏らすことで、対策は「順序を区別するならしっかり全部区別する、しないなら最後に割る」と方針を最初に決めて貫くことです。もうひとつは、数えた場合が「同様に確からしい」かの確認を怠ることです。サイコロ2個の和は 2〜12 の11通りですが、この11通りは等確率ではありません（和7は6通りの出方があるのに和2は1通り）。場合の数の比を確率にしてよいのは、数えた一つひとつが等確率のときだけ — この前提の確認こそが、数え上げを確率に変える最後の関門です。
試問
8つの数え方を、順列・組合せ・重複順列・重複組合せの4つの型に仕分けよ
項目を選んでから、入れる箱を選びます