順列と組合せ

概要

順列と組合せは、「起こりうる場合が全部で何通りあるか」を漏れなく・重複なく数え上げるための技法です。順列（permutation）は「並べる順序を区別する数え方」、組合せ（combination）は「順序を区別せず選び方だけを数える数え方」を指し、あわせて「場合の数」の計算、より広くは組合せ論（combinatorics）と呼ばれる分野の入り口にあたります。

なぜこれが統計の星図に載っているかというと、確率の最も基本的な計算方法が「事象に含まれる場合の数 ÷ 全体の場合の数」だからです。「くじで当たりを2本引く確率」「7人から3人の当番を選ぶ選び方」— こうした問いに答えるには、分子と分母の場合の数を正確に数える腕力が要ります。順列と組合せは、その数え上げを人力の書き出しから式による計算に変える道具です。

数え上げというと地味に聞こえますが、場合の数はすぐに爆発します。52枚のトランプの並べ方は52の階乗、およそ10の68乗通り — 全部書き出す戦略は最初の数個で破綻します。「書き出さずに数える」技術は、確率計算だけでなく、パスワードの強度の見積もりやアルゴリズムの計算量の評価など、爆発する可能性の空間を相手にするあらゆる場面で使われています。

なぜ生まれたか

体系的な数え上げの需要を決定的にしたのは、17世紀に確率論を生んだ賭博の問題です。「サイコロ3個の目の和が10になるのと9になるのとでは、どちらが起こりやすいか」といった問いに答えるには、目の出方を順序も含めて全部数える必要があります（和が10は27通り、9は25通り — 順序を無視して数えると同数に見えてしまい、答えを誤ります）。パスカルとフェルマーが確率を「場合の数の比」として計算し始めたとき、数え上げの正確な技法は確率論の生命線になりました。

しかし場合の数は急激に大きくなるため、書き出しによる数え上げはすぐ限界を迎えます。そこで「順序を区別するなら掛け算で数えられる」「順序を区別しないなら並べ替えのぶんだけ割ればよい」という規則が整理され、階乗・順列・組合せの記法として定式化されました。パスカルの三角形として知られる組合せの数の表は、この計算を機械的に行うための当時の早見表です。数え上げが式になったことで、確率は「原理的には計算できる」ものから「実際に計算できる」ものへと変わりました。

詳細

すべての土台 — 積の法則

数え上げの出発点は「積の法則」です。選択が段階に分かれていて、各段階の選び方が互いに影響しないなら、全体の場合の数は各段階の選択肢の数の掛け算になります。シャツ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! がそのまま定義になっています。

実務で迷ったときの判定基準はひとつだけです。「取り出した結果を入れ替えたら別物になるか？」— 役職・座席・暗証番号のように入れ替えが意味を持つなら順列、当番・くじの当たり・カードの手札のように入れ替えても同じなら組合せです。

確率計算への応用

順列と組合せが最も活躍するのは、確率の「場合の数の比」による計算です。たとえば「当たり4本を含む10本のくじから3本引いて、ちょうど当たり2本を引く確率」は、分母が 10C3 = 120通り、分子が「当たり4本から2本 × はずれ6本から1本」で 4C2 × 6C1 = 36通り、よって 36/120 = 0.3 と求まります。有名な誕生日のパラドックス（23人いれば誕生日の重複が5割超）も、「全員バラバラになる場合の数」を順列で数えて余事象を取るだけで確かめられます。直感では見当もつかない確率が、数え上げで機械的に出せるのです。

また、くじを続けて引くような問題は「1本目が当たりで、かつ2本目も当たり」という段階的な確率として条件付き確率の掛け算でも解けます。組合せで一気に数える方法と、条件付き確率で逐次掛ける方法が同じ答えに至ることを確かめると、両者の理解が一段深まります。さらに「コインを n 回投げて表がちょうど r 回出る確率」の場面では、表の出る位置の選び方 nCr がそのまま二項分布の係数になり、確率分布の世界へつながっていきます。

落とし穴 — 重複と「同様に確からしいか」

数え上げの典型的な失敗は2つあります。ひとつは同じ場合を二重に数えること・数え漏らすことで、対策は「順序を区別するならしっかり全部区別する、しないなら最後に割る」と方針を最初に決めて貫くことです。もうひとつは、数えた場合が「同様に確からしい」かの確認を怠ることです。サイコロ2個の和は 2〜12 の11通りですが、この11通りは等確率ではありません（和7は6通りの出方があるのに和2は1通り）。場合の数の比を確率にしてよいのは、数えた一つひとつが等確率のときだけ — この前提の確認こそが、数え上げを確率に変える最後の関門です。