組合せ論ワークベンチ

組み合わせ・順列計算機

nCr、nPr、重複順列、重複組合せ、スターズ・アンド・バーズ、多重集合、玉と箱、包除原理、完全順列、格子経路を計算します。

計算例 — 組合せ論ワークベンチ

正確な数	120
近似値	120
桁数	3
log10	2.0792

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

数え上げ理論 — ケース別

イエス・ノーの二問で、数え上げ問題はすべて分類できる

選ぶ(重複なし) C(n,k) = n! / (k!(n − k)!)

並べる(重複なし) P(n,k) = n! / (n − k)!

順序ありで重複あり n^k

重複ありで選ぶ C(n + k − 1, k)

選ぶ(重複なし)

公式: C(n,k) = n! / (k!(n − k)!)

計算例: 10人から3人を選びます。順序を区別しないので、C(10,3) = 120 通りの委員会です。

この例を開く: 委員会の選出

選ぶ(重複なし). 順序なしの選択:選ばれたチップは系列ではなく集合を形成する。 10人から3人を選ぶ:順序は関係ない. — 順序なしの選択:選ばれたチップは系列ではなく集合を形成する。

並べる(重複なし)

公式: P(n,k) = n! / (n − k)!

計算例: 10人の決勝進出者に金・銀・銅を割り当てます。順位が異なるので、P(10,3) = 720 通りです。

この例を開く: 表彰台の順位

並べる(重複なし). 順序ありの枠:位置を入れ替えると新しい結果になる。 10人から上位3位の表彰台を決める:順序が重要. — 順序ありの枠:位置を入れ替えると新しい結果になる。

順序ありで重複あり

公式: n^k

計算例: 10個の数字から4桁のPINを作ります。順序を区別し、数字の重複も許すので、10^4 = 10,000 通りです。

この例を開く: 暗証番号

順序ありで重複あり. 各枠は同じ集合から独立に選ぶ。 4桁の暗証番号:重複を許す. — 各枠は同じ集合から独立に選ぶ。

重複ありで選ぶ

公式: C(n + k − 1, k)

計算例: 8種類から3スクープを、順序を無視し同じ味も許して選びます。C(10,3) = 120 通りの味の多重集合です。

この例を開く: アイスクリームのスクープ

重複ありで選ぶ. 星と棒:仕切りが重複する選択を符号化する。 8種類のフレーバーから3スクープ選ぶ:順序を無視し、重複を許す. — 星と棒:仕切りが重複する選択を符号化する。

多重集合の順列

公式: N! / (n₁! · n₂! · … · n_r!)

計算例: MISSISSIPPI は11文字で、I×4、S×4、P×2、M×1です。同じ文字の交換分を割ると、11!/(4!4!2!) = 34,650 通りです。

この例を開く: MISSISSIPPI

多重集合の順列. 重複する記号は重複入れ替え分だけ順列の総数を割る。十一の文字。Sが四つ、Iが四つ、Pが二つ。式は 4!·4!·2! 分の 11! = 34,650 です。すべてが異なる文字であれば39,916,800通り。つまり、重複によって順列の99.9%以上が削ぎ落とされているのです。. — 重複する記号は重複入れ替え分だけ順列の総数を割る。

ボールを箱に入れる

公式: Σ_i=0^m (−1)ⁱC(m,i)(m − i)ⁿ

計算例: 異なる6件の仕事を3人の担当者に、全員が1件以上受け持つよう割り当てます。包除原理により 3^6 − 3·2^6 + 3 = 540 通りです。

この例を開く: 異なるものを箱へ(全射)

ボールを箱に入れる. 割り当て・分配制約のためのボールと箱のビュー。 6つの異なる作業を3人の作業者に割り当てる。全員が少なくとも1つ担当する. — 割り当て・分配制約のためのボールと箱のビュー。

包除原理

公式: C(n,k) − C(b,k)

計算例: 少なくとも1枚のエースを含む順序なしの5枚組を選びます。C(52,5) − C(48,5) = 886,656 通りです。

この例を開く: 少なくとも1枚のエース

包除原理. 加算-減算のカウントのための集合の重なりの図。余事象を使って求める、エースを少なくとも1枚含む5枚の手札. — 加算-減算のカウントのための集合の重なりの図。

特殊なケース

公式: !n = n! Σ_i=0ⁿ (−1)ⁱ / i!

計算例: 8人のSecret Santaで、誰も自分の名前を引かないよう割り当てます。完全順列の数は !8 = 14,833 通りです。

この例を開く: シークレットサンタ

特殊なケース. 古典的な制約付きの計数:円順列、完全順列、格子経路。シークレットサンタの場合の数:誰も自分の名前を引かない. — 古典的な制約付きの計数:円順列、完全順列、格子経路。

参考文献 (1)

The last case in the guide above is Secret Santa, and insight block 3 finds e hiding in it. That is the matching problem, and it is three centuries old: P. Gorroochurn, "Rencontres with Montmort (1708)", chapter 7 of Classic Problems of Probability, 54–61. Wiley, 2012 — the probability that nobody draws their own name tends to 1/e.

練習

自分で確かめる

まず答えを予想し、それから上のコントロールで確かめてください。予想を決めてから答えを開くこと。それが練習になる条件です。

10 人から 3 人を委員会に選ぶ。次に同じ 10 人から 1 位・2 位・3 位を選ぶ。n も k も同じだが、二つの総数は違うか。違うなら正確に何倍か。最初の二つのモデルで確かめてほしい。

答えを表示

120 に対して 720、6 倍である。両者を分ける問いはただ一つで、それは数ではない——順序は関係するか。順序のない 3 人の委員会は 3! = 6 通りの表彰台に並べられるので、並べることは常に選ぶことの k! 倍になる。この倍率は必ず k! であって他の何物でもなく、だからこそ二つの公式はちょうどその一回の割り算だけ違う。
10 個の数字から作る 4 桁の暗証番号と、10 種類から重複を許して選ぶアイスクリーム 4 すくい。どちらも重複を許す。どちらの総数が大きいか予想し、確かめてほしい。

答えを表示

10,000 に対して 715。どちらも重複を許すのだから、両者を分けているのは重複ではなく順序である。暗証番号は順序つき重複あり、n^k = 10⁴。すくいは順序なし重複あり、C(n + k − 1, k) = C(13,4) = 715。「重複あり」の二つのモデルは「重複なし」の二つと同じくらい離れている。だから「重複してよいか」という問いだけでは決して足りない。常に二つとも必要になる。
6 個の異なる賞品を 3 つの異なる箱に入れると 729 通り。どの箱にも最低 1 つ入るように変種を切り替えると 540 通りに落ちる。消えた 189 通りはどこへ行ったのか。

答えを表示

それはちょうど、どこかの箱が空になる入れ方である。数えるには公式ではなく符号つきの和が要る。空の箱の選び方が 3 通り、残りの詰め方が 2⁶ = 64 通りで 3 × 64 = 192。ただし 6 個すべてが一つの箱に入る 3 通りはそこで二重に数えられているので 3 を引く。残る 192 − 3 = 189 が空箱ありの入れ方で、729 − 189 = 540。この作業台で答えが交代和になる唯一のモデルであり、計算が最も遅く、手計算で最も間違えやすい。

全プロセスの詳細解説

10個から3個を選ぶ場合と7個を選ぶ場合の答え 5 ステップ
10個から3個を選ぶ方法は120通りである。順序を考慮した総数からこれを導き、さらに7個を選ぶ場合の答えもなぜ120になるのかを求めよ。
1. まずは扱いやすい順序を考慮した選び方を最初に数える。10通りの選択肢、次は9通り、その次は8通りである。
  
  $P (10, 3) = 10 \times 9 \times 8 = 720 = 3! (3 10)$
2. これは同じ3個の集合を重複して数えている。同じ3個が並び得るすべての順序の分、すなわち 3! = 6 通りずつ数えられているからである。
3. 割り算を行うと120が得られ、この k! による除算こそが順列と組合せの唯一の違いである。
  
  $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$
4. この対称性は「選ぶ」ことの意味に由来する。取るために3個を選ぶのは、残すために7個を選ぶのと全く同じ行為であるため、両者の数が異なることはあり得ない。
  
  $(3 10) = (7 10) = 120 (choosing 3 is choosing which 7 to omit)$
5. パネルに表示される log₁₀ の値 2.0792 は実用的な指標であり、3桁であることを示している。大きな n では総数が保持できる範囲を超えてオーバーフローするため、対数のみが計算可能な値として残る。
  
  $lo g_{10} 120 = 2.0792 ⟹ 3 digits$
解答

ツールには 120、3 桁、そして log₁₀ = 2.0792 と表示される。この対称性を理解しておく価値は大きい。計算の手間が半分になるからだ。C(10, 7) を一から計算する必要は誰にもない。そして行全体の合計は 2¹⁰ = 1024 となる。これは10個の要素のすべての部分集合を要素数ごとに数え上げたものであり、二項計算の整合性を確認する最も手軽な検証法となる。最大の項は C(10, 5) = 252 であり、行の中央付近が全部分集合のおよそ4分の1を占める一方、両端の項はそれぞれ1つずつしか保持しない。

$(k n) = \frac{P ( n , k )}{k !} : order costs a factor of k! = 6$
フラッシュになる5枚のカードの配り方2,598,960通り 5 ステップ
5枚の手札の配り方は 2,598,960 通り存在する。まずは順序を考慮した配り方からこれを構成し、それを用いてフラッシュの稀少性を評価する。これは n = 52、k = 5 の選ぶ（重複なし）である。
1. まず順序通りに配ることを考える。1枚目のカードの選び方は 52 通り、次は 51 通り、と続いて 48 通りまで — まだ除算は行わず、5つの因数を掛け合わせる。
  
  $P (52, 5) = 52 \times 51 \times 50 \times 49 \times 48 = 311875200$
2. 手札とは集合であり、順序を考慮した数え上げでは、同じ5枚のカードが配られ得るあらゆる順序について、各集合を 120 回ずつ重複して記録している。5! で割る操作こそが、配り方を手札へと変換する唯一のステップである。
  
  $(5 52) = \frac{311 875 200}{5 !} = \frac{311 875 200}{120} = 2598960$
3. 次に、その全空間に含まれるフラッシュの数を数える。まずスートを4通りから選び、次になかの13枚のカードから5枚を選ぶ。
  
  $flushes = 4 (5 13) = 4 \times 1287 = 5148$
4. これにより、フラッシュがなぜ稀少であるかが説明される。5,148 という手札の数が少ないからではなく、それが存在する全空間がその 500 倍も大きいからである。
  
  $P (flush) = \frac{5148}{2 598 960} = 0.00198 \approx \frac{1}{505}$
5. そして、その全空間は物理的な実感を持てるほど十分に小さい。休まず1秒に1回手札を配れば、1ヶ月以内にすべての異なる手札が出揃うことになる。
  
  $\frac{2 598 960}{86 400} = 30.1 days, at one hand per second$
解答

ツールは 2,598,960、7 桁、および log₁₀ = 6.4148 と出力する。ポーカーの役のランク付けは、まさにこの算術そのものである。ストレートも同様に数えると — 開始ランクが10通り、5枚のカードそれぞれに4つのスートがあり、10 × 4⁵ = 10,240 通り — フラッシュの2倍の数のストレートが存在することになり、これこそがフラッシュがストレートより上位とされる理由である。役の順序は意図して作られたものではなく、数え上げの結果なのである。

$(5 52) = 2598960 P (flush) \approx \frac{1}{505}$
文字の重複がない8文字のパスワード62,990,928,000通り 5 ステップ
文字の重複がない8文字のパスワードには 62,990,928,000 通りの形式がある。これを数え上げ、次にこのルールがない場合の同じパスワードを数え上げて、自分が防衛側ならどちらを選びたいかを判断する。これは n = 26、k = 8 の並べる（重複なし）である。
1. スロットを左から右へと埋めていく。1番目には 26 文字のどれでも入れられる。2番目には 25 文字が入る。使った文字はもう残っていないからである。
  
  $P (26, 8) = \frac{26 !}{18 !} = 26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19$
2. 8個の減少する因数があり、その積が答えのすべてとなる。文字の順序こそがパスワードであるため、これは組み合わせではなく順列である。
  
  $= 62990928000$
3. 次に、このルールを取り払う。各スロットは再び独立し、それぞれに 26 文字すべてが使えるようになるため、総数は単純な累乗となる。
  
  $2 6^{8} = 208827064576 (repeats allowed)$
4. 比較こそが本質である。重複を禁止することによって残る文字列は 30.2% に過ぎない。安全性を高めるように思えるルールが、10個中7個の文字列を排除してしまっているのである。
  
  $\frac{62 990 928 000}{208 827 064 576} = 0.302$
5. 攻撃者の時間スケール（1秒間に10億回の試行）で見ると、2つの空間の探索時間は1分間と3分半である。どちらも防御としては機能しておらず、しかもルールによって短い方の時間がさらに短くなっている。
  
  $1 0^{9} guesses/s : 63 s vs 209 s$
解答

n = 26、k = 8 でモデルを並べる（重複なし）に設定すると、ツールは 62,990,928,000、11 桁、および log₁₀ = 10.7993 と出力する。どのような構成ルールであっても例外なく空間を縮小させる。ルールとは禁止することしかできないからである。それが導入する価値を持つかどうかは、この算術には見えない要素、すなわち禁止された文字列が人々が偶然以上に圧倒的によく選ぶものかどうかによって決まる。よく知られたパスワードを1つ禁止すると1つの文字列が消費される。しかし、すべての重複文字を禁止すると 145,836,136,576 個もの文字列が消費される。

$P (26, 8) = 0.302 \times 2 6^{8} : forbidding repeats deletes 69.8% of the strings$
4桁のPINに対するATMでの3回の試行 5 ステップ
4桁のPINには 10,000 通りの値がある。ATMでの3回の試行がどれほどの価値を持つか、そして数字の重複を避けるというよくある助言に実際どれほどのコストがかかるかを計算する。これは n = 10、k = 4 の順序あり（重複あり）である。
1. 4つのスロットがあり、それぞれに10個の数字が使え、互いに何ら影響しない — 直前に使った数字も、次のスロットで再び使用できる。
  
  $10 \times 10 \times 10 \times 10 = 1 0^{4} = 10000$
2. したがって、一様に選ばれたPINに対して3回試行する場合、当たる確率は 10,000 分の3となる。3回制限は、無制限な推測を単に改善したものではない。この空間においては、それ自体が防御のすべてなのである。
  
  $3 attempts : \frac{3}{10 000} = 0.03%$
3. ここで「重複文字なし」というルールを課してみる。選択肢は10通り、次に9通り、8通り、7通りとなる。
  
  $no repeated digit : 10 \times 9 \times 8 \times 7 = 5040$
4. このルールにより 5,040 通りのPINが残り、4,960 通りが破棄される。空間の半分が消え去り、失われた半分には 1111 をはじめとする他のすべての重複パターンが含まれていた。
  
  $\frac{5040}{10 000} = 0.504$
5. 桁数を2つ増やすことは、試行回数を2回増やすことではない。桁が1つ増えるごとに選択肢は10倍になるため、6桁のPINの空間は 100 倍になる。
  
  $six digits : 1 0^{6} = 1000000 = 100 \times 1 0^{4}$
解答

ツールは n = 10、k = 4 に対し 10,000 と出力する。2つの事実が同時に成り立つ。すなわち、空間はきわめて小さいが、PINは通常それでも問題ない — なぜなら、3回の試行制限により、攻撃者に与えられるのは全体の100%ではなく 0.03% に過ぎないからである。しかし脅威モデルを変えれば結論は逆転する。漏洩したPINのファイルには試行制限がなく、10,000 通りの候補の検証など1秒未満の作業である。これこそが、PINの安全性がPINそのものだけに依存することが決してない理由である。

$n^{k} = 1 0^{4} = 1000010 \times 9 \times 8 \times 7 = 5040$
8種類の味から3つのスクープと10人から3人 5 ステップ
8種類のフレーバーから重複を許して3スクープを選ぶのは120通りであり、これは10人から3人を選ぶ通り数と同じである。これが偶然ではないことを示せ。これは n = 8、k = 3 の重複組合せである。
1. 注文を記号の列として書き表す。スクープ1つにつき1つの星、次のフレーバーに移動するステップ1回につき1つの仕切り線を割り当てる。8種類のフレーバーから3スクープを選ぶには、3つの星と7つの仕切り線が必要となる。
  
  $3 scoops ⋆ ⋆ ⋆ and 7 bars ∣ ∣ ∣ ∣ ∣ ∣ ∣$
2. これら10個の記号のそれぞれの並べ替えが1つの注文に対応し、すべての注文が1つの並べ替えに対応する。したがって、問題は10個の位置のうちどの3個に星を配置するかということだけに帰着される。これは、名詞が異なるだけで問題1の問いと同じである。
  
  $(3 3 + 7) = (3 10) = 120$
3. 重複を禁止すると、通り数は56に減少する。フレーバーの重複を許可すると注文がさらに64通り増え、メニューの全注文数は2倍以上に膨れ上がる。
  
  $(3 8) = 56 (no repeats allowed)$
4. ここで順序も区別することにし、バニラ・バニラ・ミントとミント・バニラ・バニラを異なるものとする。これは8通りの独立した選択を3回繰り返すことに相当する。
  
  $8^{3} = 512 (ordered, repeats allowed)$
5. これら2つの比率は 4.27 であり、3! = 6 ではない。重複するスクープを含むコーンは、3つの異なるスクープを持つコーンよりも区別できる並べ替えの数が少なくなる。したがって、3! で割るという操作は、まさにここでは行ってはならないステップである。
  
  $\frac{512}{120} = 4.27 \neq = 3! = 6$
解答

ツールには 120、3 桁、log₁₀ = 2.0792 と表示される。これは別の問いでありながら問題1と同じ表示結果である。スターとバーは公式というより変換法である。重複という概念を位置へと置き換えるものであり、位置の扱い方はすでに知られている。この方法が仕掛ける罠はステップ5にある。重複が許可されると並べ替えの同等性が失われるため、順序を考慮した数と考慮しない数の間を変換する単一の係数は存在しない。

$(k n + k - 1) : k stars, n - 1 bars$
4つのSが隣り合わないMISSISSIPPIの34,650通りの文字列 5 ステップ
MISSISSIPPI の文字からは、34,650 通りの異なる単語が作られる。これを導出し、次に出力欄のないより難解な問いに答えよ。4つの S が互いに隣り合わないのはどのくらいの割合か？これは個数が 1, 4, 4, 2 の同じものを含む順列である。
1. まずはすべての文字が区別可能であるとみなす。S に S₁ から S₄ までのラベルを付与する。そうすれば、これは11個の要素の単純な順列となる。
  
  $11! = 39916800$
2. 次にラベルを取り外す。4つの S は書かれている文字列を変えることなく 4! 通りに並べ替えることができ、4つの I と 2つの P についても同様である。したがって、表示される各単語は 1,152 回ずつ重複して数えられていたことになる。
  
  $\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1152} = 34650$
3. これにより確率が直接得られる。11枚のタイルをシャッフルしたとき、34,650 通りの配置のうちの1つがこの州の名を綴る。
  
  $P (a shuffle spells MISSISSIPPI) = \frac{1}{34 650} = 0.0000289$
4. より難しい問いについては、まず他の7文字（M、4つの I、2つの P）を先に配置し、その並べ方を数える。これにより両端を含めて8つの隙間が生じ、各 S はそれぞれ異なる隙間に入らなければならない。
  
  $\frac{7 !}{1 ! 4 ! 2 !} = 105, (4 8) = 70$
5. 乗算と除算を行う。34,650 通りの単語のうち 7,350 通りにおいて S 同士が隣り合わず離れており、これは 21.2% に相当する。
  
  $\frac{105 \times 70}{34 650} = \frac{7350}{34 650} = 0.2121 = \frac{7}{33}$
解答

ツールには 34,650、5 桁、log₁₀ = 4.5397 と表示される。ステップ4と5の隙間法は、得られる答えそのもの以上の価値がある。これはどの2つも隣り合わないという条件全般に使える一般的な手立てである。制約のない要素を先に配置し、次に制約のある要素を入れる隙間を選ぶ。隣接という条件はどの階乗でも表現できないが、隙間によって位置の選択へと変換される。そして位置の選択は、このページのあらゆる公式がすでに数え方を知っている唯一のことである。

$\frac{n !}{n _{1} ! n _{2} ! \dots} : divide by the orderings you cannot see$
誰も休まない、3人の作業員への6つの異なるタスクの割り当て 5 ステップ
誰も空きが出ないように6つの異なるタスクを3人の作業員に割り当てる方法は540通りである。適切なケースを直接数えるのではなく、不適なケースを取り除くことでこれを導出せよ。これは n = 6、m = 3 で、区別のある物体、すべての箱を使用する球と箱の問題である。
1. まずは条件を無視する。各タスクは独立して3人の作業員のいずれか1人を選ぶため、制約のない通り数は累乗となり、制約がある場合よりもはるかに容易に求まる。
  
  $3^{6} = 729 (no restriction)$
2. 次に、誰かの仕事が空になる割り当てを引き去る。空の作業員の選び方が3通りあり、その上で6つすべてのタスクを残りの2人に割り当てる。
  
  $one worker idle : (1 3) 2^{6} = 3 \times 64 = 192$
3. その引き算は行き過ぎであった。1人の作業員しか使わない割り当ては、空にされた同僚の分としてそれぞれ2回引かれていたため、それら3通りを書き戻す。
  
  $two idle, added back : (2 3) 1^{6} = 3$
4. 減算と加算を交互に行う操作は包除原理であり、ツール内の公式行に表示されているのはこの交互和である。
  
  $729 - 192 + 3 = 540$
5. したがって、全割り当ての4分の3が結果的に全員を使用する。作業員の区別をなくすために 3! で割ると、第二種スターリング数 S(6, 3) = 90 が得られる。色は名前なしで数えた同じ分割である。
  
  $\frac{540}{729} = 0.7407, S (6, 3) = \frac{540}{3 !} = 90$
解答

ツールには 540、3 桁、log₁₀ = 2.7324 と表示される。この問題でつまずきやすいのはステップ3である。不適なケースを引くことが手法そのものだと勘違いしがちだが、そうではない。重なり合う集合における引き算は必ず引き過ぎてしまうため、補正項は飾りではない。ステップ5の 90 は同じ対象を別の視点から見たものである。名前付きの作業員なら 540 通りの割り当て、名前がなければ 90 通りの分割となり、両者の差はまさに名前の割り当て方である 3! 通りに相当する。

$i = 0 \sum m (- 1)^{i} (i m) (m - i)^{n} = 540 = 3! S (6, 3)$
空の箱がない、区別された4つの箱への12個の同じトークンの入れ方 5 ステップ
区別できない12個のトークンを空の箱がないように区別された4つの箱に分配する方法は165通りである。あらかじめ制約を満たすことで解に到達する。これは、n = 12およびm = 4の、区別できない物体、空箱なしのボールと箱問題である。
1. どの箱にも少なくとも1個入れるという条件があるため、即座にそれを満たす。各箱にトークンを1個ずつ入れ、それ以上考えないようにする。残りは8個のトークンとなり、ここからはルールが一切なくなる。
  
  $pay the floor first : 12 - 4 = 8 units still free$
2. 区別できないアイテムを自由に分配するのは「星と棒（stars and bars）」の考え方であり、4つの箱を仕切るために8個の星と3本の棒を用いる。その総数は棒をどの位置に配置するかの選択肢の数である。
  
  $(4 - 1 8 + 4 - 1) = (3 11) = 165$
3. 「空箱なし」のルールを取り払うと、12個のトークンがすべて自由になるため、同じ方法により455通りが得られる。
  
  $without the floor : (3 12 + 4 - 1) = (3 15) = 455$
4. したがって、各箱に最低1個という下限を設けると、すべての分配のほぼ3分の2が除外され、455通りのうち165通りだけが残る。
  
  $\frac{165}{455} = 0.363$
5. 代わりにトークンを区別できるようにすると、総数は16,777,216通りへと跳ね上がる。12個の物体において、区別不能性は大きな影響を持ち、実に5桁もの差が生じる。
  
  $distinct units instead : 4^{12} = 16777216$
解答

ツールには165、3桁、およびlog₁₀ = 2.2175と表示される。ステップ1は他に応用可能な手段である。各部分に対する下限はあらかじめ支払う（満たす）ことができる。なぜなら、それを支払うことで、より小さなnを持つ同じ構造の問題が残るだけだからである。下限をそれぞれ3個ずつに引き上げると、12から12を差し引いて残りは0となり、答えは1通りとなる。これは逆方向には成り立たず、その非対称性こそが、1箱あたり高々2個という問いが少なくとも1個よりも難題である理由のすべてである。

$(m - 1 n - 1) : a floor of one is a constant, not a new formula$
少なくとも1枚のエースを含む5枚のカードの手札886,656通り 5 ステップ
少なくとも1枚のエースを含む5枚の手札は886,656通り存在する。エースを含まない手札の数を数えて全体から引き、検証として同じ数値を愚直な方法で再構築する。これはn = 52、k = 5、およびエース以外の48枚のカードを用いた、少なくとも1枚に関する包除原理問題である。
1. 少なくとも1枚のエースを含む手札を直接数えるには、エースが1枚、2枚、3枚、4枚の場合に分類することを意味する。補集合を数える計算は1回で済むため、まずそこから始める。
  
  $(5 52) = 2598960$
2. エースを全く含まない手札は、エース以外の48枚のカードから引いた5枚である。
  
  $(5 48) = 1712304 (not one ace)$
3. 全体からこれを引くと、残ったすべての手札にエースが含まれることになる。手札にはエースが全く含まれないか、少なくとも1枚含まれるかのどちらかであり、その中間の状態は存在しないからである。
  
  $2598960 - 1712304 = 886656$
4. したがって、全手札の3分の1が少なくとも1枚のエースを含んでおり、これは52枚のカードに4枚のエースというフレーズが示唆するよりもはるかに多い。
  
  $P = \frac{886 656}{2 598 960} = 0.3412$
5. 次に検証を行う。エースがちょうど1枚、ちょうど2枚、ちょうど3枚、ちょうど4枚の場合をそれぞれ数えて加算する。4つの独立した計算を行うと、合計は最後の1桁まで一致する。
  
  $4 (4 48) + 6 (3 48) + 4 (2 48) + (1 48) = 778320 + 103776 + 4512 + 48 = 886656$
解答

ツールには886,656、6桁、およびlog₁₀ = 5.9478と表示される。ステップ5は単なる飾りではない。少なくとも1つというフレーズは、4 × C(48, 4) = 778,320（エースを1枚選び、その周囲を埋める）と最もよく誤って計算される。しかし、この手順ではエースが2枚ある手札がそれぞれのエースから1回ずつ、計2回生成されるため、その数値は誤りである。補集合を使えばそのような過ちを犯す心配がないため、問題に少なくとも1つとある場合には真っ先に補集合を活用すべきである。

$∣ A ∣ = N - ∣ A^{c} ∣ : count the easy side and subtract$
3つのクラブにまたがる40人、35人、28人のメンバー 5 ステップ
3つのクラブのメンバー数が40人、35人、28人であっても、実際の人数は103人ではない。実際の人数を求め、それを1つのクラブ、2つのクラブ、または3つすべてのクラブに所属する人に分類する。これは、2集合間の重複が12、10、9であり、3集合の重複が4である、3集合の和集合に関する包除原理問題である。
1. 3つの名簿の人数を足し合わせる。2つのクラブに所属する人は2回カウントされ、3つすべてに所属する人は3回カウントされているため、103という数値は上限に過ぎない。
  
  $40 + 35 + 28 = 103$
2. 各2集合の重複分を差し引く。これにより、ちょうど2つのクラブに所属する人は正しくカウントされるが、3つすべてに所属する人は3回カウントされて3回差し引かれたため、完全に消えてしまう。
  
  $103 - (12 + 10 + 9) = 103 - 31 = 72$
3. 彼らを元に戻すために、3集合の重複分を再び加算する。これが3つの集合における包除原理のすべてである。すなわち、単体を足し、ペアを引き、トリプルを足すのである。
  
  $72 + ∣ A \cap B \cap C ∣ = 72 + 4 = 76$
4. 和集合の数値だけではこれら76人の詳細な内訳までは分からないが、同じ3つの入力値からそれも導くことができる。ペアの重みを2倍、トリプルの重みを3倍にして差し引くことで、複数のクラブに所属している全員を除外する。
  
  $exactly one = 103 - 2 (31) + 3 (4) = 53$
5. 残りは自ずと導かれる。ちょうど2つのクラブに所属する人は19人であり、3つのグループを足し合わせると76人に戻る。
  
  $exactly two = 31 - 3 (4) = 19, 53 + 19 + 4 = 76$
解答

ツールには76、2桁、およびlog₁₀ = 1.8808と表示される。符号の交互変化は暗記のための語呂合わせではなく、修正作業である。各項が直前の項の過剰分を修正し、その修正が逆方向に過剰となるため符号が交互入れ替わるのである。公式の項数がこれほど急速に増大するのもそれが理由である。4つの集合では15個の項が必要であり、n個の集合では2ⁿ − 1個の項が必要となる。それが実用的でなくなるよりずっと前に、問題9の補集合の方がより優れた道具となる。

$∣ A \cup B \cup C ∣ = Σ_{1} - Σ_{2} + Σ_{3} = 76$
誰も自分の名前を引かない、8人で行うシークレットサンタのくじ引き 5 ステップ
8人がシークレットサンタのくじ引きを行い、起こり得る40,320通りの引き方のうち、自分の名前を引いた人が1人もいないのは14,833通りである。この通り数を導出し、次に通常は何人が自分の名前を引くことになるかを求めよ。これは特別なケース、n = 8 の完全順列である。
1. 完全順列とは、不動点を持たない順列のことである。8つの「この人が自分の名前を引く」という事象に対して包除原理を適用すると、交代和が得られる。
  
  $! n = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}$
2. その和は e⁻¹ の級数の最初の9項であり、省略された残りの部分はすべて 1/9! = 2.8 × 10⁻⁶ より小さい。
  
  $8! = 40320, i = 0 \sum 8 \frac{( - 1 ) ^{i}}{i !} = 0.367882$
3. これを計算して四捨五入すると、誰も自分の名前を持っていない引き方は 14,833 通りとなる。
  
  $! 8 = 40320 \times 0.367882 = 14833$
4. 割合にすると 0.36788 であり、e⁻¹ = 0.367879 に対して 8人の時点で小数第5位まで一致し、より大きなグループになってもほとんど変化しない。
  
  $P = \frac{14 833}{40 320} = 0.36788 \approx e^{- 1} = 0.367879$
5. ここで、より簡単な別の問いを考える。各人が自分の名前を引く確率は 1/n であり、事象が独立であるかどうかに関わらず期待値には加法性が成り立つため、自分自身を引く人数の期待値は、8人であっても800人であっても正確に 1 となる。
  
  $E [self-draws] = i = 1 \sum n \frac{1}{n} = n \times \frac{1}{n} = 1$
解答

ツールは 14,833、桁数 5、および log₁₀ = 4.1712 を出力する。ステップ5はステップ4の理由を説明している。グループの大きさに関わらず自分自身を引く人数の平均が 1 であるなら、誰1人引かない確率はグループの大きさにあまり依存し得ない。そして平均 1 の稀事象の回数において、その確率は e⁻¹ となる。この定数は単なる珍しい性質ではない。これは「平均が1であるとき、0となる確率はどれくらいか」という、組合せ論の枠を超えて頻繁に現れる問いに対する答えなのである。

$\frac{! n}{n !} \to e^{- 1}, E [self-draws] = 1 for every n$
1つのマスが塞がれた7 × 5のグリッド上の最短経路 5 ステップ
1つのセルが通行不可である場合、7 × 5 の格子を横断する最短経路は 442 通りある。すべての経路数を求め、通行不可のセルを通る経路数を求めて差し引け。次に、最も影響が大きいセルを特定せよ。これは特別なケースの格子経路であり、東へ 7 ステップ、北へ 5 ステップ進み、(3, 2) がブロックされている。
1. どの最短経路も長さは12ステップであり、そのうち7ステップが東、5ステップが北へ進む順序に対応する。したがって経路を決めることは、どのステップを東進とするかを選択することにほかならない。
  
  $(7 7 + 5) = (7 12) = 792$
2. 通行不可のセルを通る経路は、そのセルで結合された2つの独立した経路（角からそのセルまで、およびそのセルから反対側の角まで）に分解できる。前半のすべての経路が後半のすべての経路と組み合わされるため、これらを掛け合わせる。
  
  $through (3, 2) : (3 5) (4 7) = 10 \times 35 = 350$
3. 全体からこれを引き算すれば、残るものはまさにそのセルを通らない経路となる。
  
  $792 - 350 = 442$
4. その1つのセルは全トラフィックの 44% を担っていた。つまり、1箇所が通行不可になるだけで、経路のほぼ半分が失われる。
  
  $\frac{350}{792} = 0.442$
5. しかし、失われて最も影響が大きいセルはそこではない。スタートから東に1ステップ進んだ位置にあるセルは 462 通り（全体の 58%）の経路を担っている。なぜなら、東進で始まるすべての経路がそこを通過しなければならないからである。
  
  $through (1, 0) : (1 1) (6 11) = 462 = 0.583 of all paths$
解答

ツールは 442、桁数 3、および log₁₀ = 2.6454 を出力する。ステップ5は直感的な見た目と矛盾する。通行不可のセルは経路が集中して見える中央付近で最も影響が大きいように思われるが、計算によれば角に近いセルのほうがより多くの経路を担っている。なぜなら、あるセルを通る経路数は2つの二項係数の積であり、角に近い位置ではそのうち1つが格子ほぼ全体をカバーするからである。マップを眺めるのではなく各ノードを通る経路数を計算する手法は、実際のネットワークで冗長性を測定する方法でもある。

$(a a + b) - (x x + y) (a - x ( a - x ) + ( b - y )) = 442$

42Math チーム · 更新 2026-08-17

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

統計・ファイナンスのレッスン一覧 →

例題

委員会の選出 - 10人から3人を選ぶ:順序は関係ない
5枚のカードの手札 - ポーカーの手札は2,598,960通りあります。ツールはその傍らに、数の規模として「7桁、log₁₀ 6.4148」と出力します。そして、結果空間が大きすぎるとして列挙を拒みます。その拒否こそが、この一行の主題です。集合を実際に構築することなく、公式が総数を教えてくれるのです。
宝くじの選択 - 宝くじの選び方
表彰台の順位 - 10人から上位3位の表彰台を決める:順序が重要
重複なしパスワード - 重複のないパスワード
全て並べる - 全体を並べる
暗証番号 - 4桁の暗証番号:重複を許す
商品コード - 製品コード
アイスクリームのスクープ - 8種類のフレーバーから3スクープ選ぶ:順序を無視し、重複を許す
同一のボール - 区別のないボール
BALLOON - 重複する文字を含むBALLOONの並べ方
MISSISSIPPI - 十一の文字。Sが四つ、Iが四つ、Pが二つ。式は 4!·4!·2! 分の 11! = 34,650 です。すべてが異なる文字であれば39,916,800通り。つまり、重複によって順列の99.9%以上が削ぎ落とされているのです。
異なるものを箱へ(制約なし) - 区別のある箱に分配(任意)
異なるものを箱へ(全射) - 6つの異なる作業を3人の作業者に割り当てる。全員が少なくとも1つ担当する
同一のものを箱へ(制約なし) - 区別のない箱に分配(任意)
同一のものを箱へ(空を許さない) - 区別のない箱に分配(空箱なし)
少なくとも1枚のエース - 余事象を使って求める、エースを少なくとも1枚含む5枚の手札
3集合の和集合 - 3つの集合の和集合
円卓 - 7人を円卓に座らせる:回転は同一とみなす
シークレットサンタ - シークレットサンタの場合の数:誰も自分の名前を引かない
格子経路 - 通行止めのマスを1つ避けながら格子上の最短経路を数える