組み合わせ・順列計算機

まず順序通りに配ることを考える。1枚目のカードの選び方は 52 通り、次は 51 通り、と続いて 48 通りまで — まだ除算は行わず、5つの因数を掛け合わせる。

手札とは集合であり、順序を考慮した数え上げでは、同じ5枚のカードが配られ得るあらゆる順序について、各集合を 120 回ずつ重複して記録している。5! で割る操作こそが、配り方を手札へと変換する唯一のステップである。

次に、その全空間に含まれるフラッシュの数を数える。まずスートを4通りから選び、次になかの13枚のカードから5枚を選ぶ。

これにより、フラッシュがなぜ稀少であるかが説明される。5,148 という手札の数が少ないからではなく、それが存在する全空間がその 500 倍も大きいからである。

そして、その全空間は物理的な実感を持てるほど十分に小さい。休まず1秒に1回手札を配れば、1ヶ月以内にすべての異なる手札が出揃うことになる。

スロットを左から右へと埋めていく。1番目には 26 文字のどれでも入れられる。2番目には 25 文字が入る。使った文字はもう残っていないからである。

8個の減少する因数があり、その積が答えのすべてとなる。文字の順序こそがパスワードであるため、これは組み合わせではなく順列である。

次に、このルールを取り払う。各スロットは再び独立し、それぞれに 26 文字すべてが使えるようになるため、総数は単純な累乗となる。

比較こそが本質である。重複を禁止することによって残る文字列は 30.2% に過ぎない。安全性を高めるように思えるルールが、10個中7個の文字列を排除してしまっているのである。

攻撃者の時間スケール（1秒間に10億回の試行）で見ると、2つの空間の探索時間は1分間と3分半である。どちらも防御としては機能しておらず、しかもルールによって短い方の時間がさらに短くなっている。

4つのスロットがあり、それぞれに10個の数字が使え、互いに何ら影響しない — 直前に使った数字も、次のスロットで再び使用できる。

したがって、一様に選ばれたPINに対して3回試行する場合、当たる確率は 10,000 分の3となる。3回制限は、無制限な推測を単に改善したものではない。この空間においては、それ自体が防御のすべてなのである。

ここで「重複文字なし」というルールを課してみる。選択肢は10通り、次に9通り、8通り、7通りとなる。

このルールにより 5,040 通りのPINが残り、4,960 通りが破棄される。空間の半分が消え去り、失われた半分には 1111 をはじめとする他のすべての重複パターンが含まれていた。

桁数を2つ増やすことは、試行回数を2回増やすことではない。桁が1つ増えるごとに選択肢は10倍になるため、6桁のPINの空間は 100 倍になる。

注文を記号の列として書き表す。スクープ1つにつき1つの星、次のフレーバーに移動するステップ1回につき1つの仕切り線を割り当てる。8種類のフレーバーから3スクープを選ぶには、3つの星と7つの仕切り線が必要となる。

これら10個の記号のそれぞれの並べ替えが1つの注文に対応し、すべての注文が1つの並べ替えに対応する。したがって、問題は10個の位置のうちどの3個に星を配置するかということだけに帰着される。これは、名詞が異なるだけで問題1の問いと同じである。

重複を禁止すると、通り数は56に減少する。フレーバーの重複を許可すると注文がさらに64通り増え、メニューの全注文数は2倍以上に膨れ上がる。

ここで順序も区別することにし、バニラ・バニラ・ミントとミント・バニラ・バニラを異なるものとする。これは8通りの独立した選択を3回繰り返すことに相当する。

これら2つの比率は 4.27 であり、3! = 6 ではない。重複するスクープを含むコーンは、3つの異なるスクープを持つコーンよりも区別できる並べ替えの数が少なくなる。したがって、3! で割るという操作は、まさにここでは行ってはならないステップである。

まずはすべての文字が区別可能であるとみなす。S に S₁ から S₄ までのラベルを付与する。そうすれば、これは11個の要素の単純な順列となる。

次にラベルを取り外す。4つの S は書かれている文字列を変えることなく 4! 通りに並べ替えることができ、4つの I と 2つの P についても同様である。したがって、表示される各単語は 1,152 回ずつ重複して数えられていたことになる。

これにより確率が直接得られる。11枚のタイルをシャッフルしたとき、34,650 通りの配置のうちの1つがこの州の名を綴る。

より難しい問いについては、まず他の7文字（M、4つの I、2つの P）を先に配置し、その並べ方を数える。これにより両端を含めて8つの隙間が生じ、各 S はそれぞれ異なる隙間に入らなければならない。

乗算と除算を行う。34,650 通りの単語のうち 7,350 通りにおいて S 同士が隣り合わず離れており、これは 21.2% に相当する。

まずは条件を無視する。各タスクは独立して3人の作業員のいずれか1人を選ぶため、制約のない通り数は累乗となり、制約がある場合よりもはるかに容易に求まる。

次に、誰かの仕事が空になる割り当てを引き去る。空の作業員の選び方が3通りあり、その上で6つすべてのタスクを残りの2人に割り当てる。

その引き算は行き過ぎであった。1人の作業員しか使わない割り当ては、空にされた同僚の分としてそれぞれ2回引かれていたため、それら3通りを書き戻す。

減算と加算を交互に行う操作は包除原理であり、ツール内の公式行に表示されているのはこの交互和である。

したがって、全割り当ての4分の3が結果的に全員を使用する。作業員の区別をなくすために 3! で割ると、第二種スターリング数 S(6, 3) = 90 が得られる。色は名前なしで数えた同じ分割である。

どの箱にも少なくとも1個入れるという条件があるため、即座にそれを満たす。各箱にトークンを1個ずつ入れ、それ以上考えないようにする。残りは8個のトークンとなり、ここからはルールが一切なくなる。

区別できないアイテムを自由に分配するのは「星と棒（stars and bars）」の考え方であり、4つの箱を仕切るために8個の星と3本の棒を用いる。その総数は棒をどの位置に配置するかの選択肢の数である。

「空箱なし」のルールを取り払うと、12個のトークンがすべて自由になるため、同じ方法により455通りが得られる。

したがって、各箱に最低1個という下限を設けると、すべての分配のほぼ3分の2が除外され、455通りのうち165通りだけが残る。

代わりにトークンを区別できるようにすると、総数は16,777,216通りへと跳ね上がる。12個の物体において、区別不能性は大きな影響を持ち、実に5桁もの差が生じる。

少なくとも1枚のエースを含む手札を直接数えるには、エースが1枚、2枚、3枚、4枚の場合に分類することを意味する。補集合を数える計算は1回で済むため、まずそこから始める。

エースを全く含まない手札は、エース以外の48枚のカードから引いた5枚である。

全体からこれを引くと、残ったすべての手札にエースが含まれることになる。手札にはエースが全く含まれないか、少なくとも1枚含まれるかのどちらかであり、その中間の状態は存在しないからである。

したがって、全手札の3分の1が少なくとも1枚のエースを含んでおり、これは52枚のカードに4枚のエースというフレーズが示唆するよりもはるかに多い。

次に検証を行う。エースがちょうど1枚、ちょうど2枚、ちょうど3枚、ちょうど4枚の場合をそれぞれ数えて加算する。4つの独立した計算を行うと、合計は最後の1桁まで一致する。

3つの名簿の人数を足し合わせる。2つのクラブに所属する人は2回カウントされ、3つすべてに所属する人は3回カウントされているため、103という数値は上限に過ぎない。

各2集合の重複分を差し引く。これにより、ちょうど2つのクラブに所属する人は正しくカウントされるが、3つすべてに所属する人は3回カウントされて3回差し引かれたため、完全に消えてしまう。

彼らを元に戻すために、3集合の重複分を再び加算する。これが3つの集合における包除原理のすべてである。すなわち、単体を足し、ペアを引き、トリプルを足すのである。

和集合の数値だけではこれら76人の詳細な内訳までは分からないが、同じ3つの入力値からそれも導くことができる。ペアの重みを2倍、トリプルの重みを3倍にして差し引くことで、複数のクラブに所属している全員を除外する。

残りは自ずと導かれる。ちょうど2つのクラブに所属する人は19人であり、3つのグループを足し合わせると76人に戻る。

完全順列とは、不動点を持たない順列のことである。8つの「この人が自分の名前を引く」という事象に対して包除原理を適用すると、交代和が得られる。

その和は e⁻¹ の級数の最初の9項であり、省略された残りの部分はすべて 1/9! = 2.8 × 10⁻⁶ より小さい。

これを計算して四捨五入すると、誰も自分の名前を持っていない引き方は 14,833 通りとなる。

割合にすると 0.36788 であり、e⁻¹ = 0.367879 に対して 8人の時点で小数第5位まで一致し、より大きなグループになってもほとんど変化しない。

ここで、より簡単な別の問いを考える。各人が自分の名前を引く確率は 1/n であり、事象が独立であるかどうかに関わらず期待値には加法性が成り立つため、自分自身を引く人数の期待値は、8人であっても800人であっても正確に 1 となる。

どの最短経路も長さは12ステップであり、そのうち7ステップが東、5ステップが北へ進む順序に対応する。したがって経路を決めることは、どのステップを東進とするかを選択することにほかならない。

通行不可のセルを通る経路は、そのセルで結合された2つの独立した経路（角からそのセルまで、およびそのセルから反対側の角まで）に分解できる。前半のすべての経路が後半のすべての経路と組み合わされるため、これらを掛け合わせる。

全体からこれを引き算すれば、残るものはまさにそのセルを通らない経路となる。

その1つのセルは全トラフィックの 44% を担っていた。つまり、1箇所が通行不可になるだけで、経路のほぼ半分が失われる。

しかし、失われて最も影響が大きいセルはそこではない。スタートから東に1ステップ進んだ位置にあるセルは 462 通り（全体の 58%）の経路を担っている。なぜなら、東進で始まるすべての経路がそこを通過しなければならないからである。