二つの規則
すべては和か積である
互いに交わらない場合分けは足し、独立な段階は掛けます。「または」は和、「かつ」は積の合図です。以下の式はすべて、この二つの規則に「二重に数えた分の補正」を加えただけのものです。
A ∩ B = ∅ のとき |A ∪ B| = |A| + |B| · 段階的な選択なら n₁n₂⋯nk積の規則が数えているのは対象ではなく手順です。ひとつの対象がちょうど d 通りの手順から生じるなら、d で割ります。この割り算こそ C(n,k) の出どころです。
インタラクティブ組合せ論
選んで数え、
重複で割る。
順列、組合せ、パスカルの三角形、二項定理、仕切りと星は、ひとつの原理が姿を変えたものです。有限集合の上の確率は、その数え上げを割ったものにすぎません。
統一する考え対象を独立な選択の列として記述し、選択肢の数を掛け合わせ、同じ対象を何通りの手順で作ったかで割ります。
順序が重要なとき
P(n,k) は縮んでいく選択肢
n 通り、次に n−1 通り、次に n−2 通り。階乗の商ではなく積として書きましょう。P(9,3) = 9·8·7 = 504 のほうが 9!/6! より速く、間違えにくいのです。
順序が無関係なとき
C(n,k) は k! で割る
順序のない k 個の組は、その k! 通りの並べ方ごとに一度ずつ数えられています。どの組でも同じ回数なので、この割り算は近似ではなく厳密です。
二重数え上げ
ひとつの集合を二通りに数える
パスカルの法則、ホッケースティック、ヴァンデルモンド、平方和の等式は、証明がすべて同じ形です。集合をひとつ用意し、二通りに数え、両者が等しいと結論します。階乗を変形するより短く、見通しも良くなります。
二項定理
係数が「個数」である理由
(x+y)n の展開とは、n 個の括弧それぞれから x か y を選ぶことです。項が xn−kyk になるのは、ちょうど k 個の括弧から y を選んだときであり、その選び方は C(n,k) 通りあります。
(x + y)n = Σ C(n,k) xn−k yk仕切りと星
順序なし・重複あり
n 個の対象を星として並べ、r−1 本の仕切りで区切ります。並べ方は x₁ + ⋯ + xr = n の解と一対一に対応するので、答えは C(n+r−1, r−1) です。
数え上げから確率へ
同様に確からしいとは、数えて割ることである
有限標本空間で各結果が同様に確からしいなら、P(A) = |A| / |S| です。5枚のポーカーの手は純粋な数え上げの練習であり、9つの分類の合計はちょうど C(52,5) = 2,598,960 になります。これが「場合分けが互いに交わらず、かつ尽くされている」ことの検算になります。
結果が同様に確からしくなくなれば公理が必要になり、平均を求めたくなれば期待値が必要になります。しかし数え上げが消えることはありません。
期待値
指示関数、そして線形性
起こりうる事柄ごとに指示関数を用意して X をその和として書き、E[Σ Xᵢ] = Σ E[Xᵢ] を使います。独立性は不要です。だからこそ、分布そのものは手に負えない問題でも解けるのです。
分布
ひとつの実験、六つの問い
二項分布は n 回の試行での成功数を数え、幾何分布は最初の成功を待ち、負の二項分布は r 回目の成功を待ちます。超幾何分布は復元を外し、ポアソン分布は稀な事象の極限です。どの確率関数も、前半の数え上げの恒等式によって総和が 1 になります。
実際に起きる間違い
答えを確定する前に確かめる五点
- 二度割る。すでに C(n,k) と書いたなら順序は消えています。さらに k! で割ってはいけません。
- 名前のある組と名前のない組。12人を4人ずつの「名前のある」3チームに分ける場合と、名前のない3グループに分ける場合は別物です。後者は 3! で割ります。
- 重なる場合分け。和の規則は互いに交わらない場合を要求します。「Aliceを含む、またはBobを含む」は二重に数えます。包除原理を使いましょう。
- 条件を入れ替える。P(A | B) は P(B | A) ではありません。両者は P(A)/P(B) 倍だけ違います。
- 情報の出し方を無視する。得られたのは事実そのものではなく、何らかの仕組みが報告した事実です。モンティ・ホール問題も二人の子の問題も、まさにここが要点です。
印刷版
38ページ、すべて計算済み
PDF版では同じ範囲をより詳しく扱います。数え上げの規則、順列と組合せ、パスカルの恒等式、二項定理と多項定理、仕切りと星、包除原理と完全順列、全単射とカタラン数。続いて確率を公理からベイズ、期待値、分散、名前のついた分布、古典的問題まで展開します。最後に公式一覧、判断のための決定木、そして完全解答つきの24問を収めています。数値はすべて、組版の前に厳密計算で検証しました。