組み合わせ計算

組み合わせ：C(n, r) = n! / (r!(n − r)!) · 順列：P(n, r) = n! / (n − r)! · 重複を許す場合：C = (n + r − 1)! / (r!(n − 1)!)、P = nʳ

n

選ぶ対象になる異なる項目の数です。選ぶ回数ではなく母集団の大きさにあたり、重複を許す組み合わせではこの数が実質的に増えます

r

選ぶ項目の数です。重複を許さないとき、rはnを超えられません。重複を許すときは同じ項目が2度現れてよいので、rはnより大きくてもかまいません

allow repetition

同じ項目を2度以上選んでよいかどうかです。これは表示の好みではなく、別の式を選ぶスイッチです。そしてrがnより大きいことが合法なのか不可能なのかを決める設定でもあります

C(n, r)

nCrとして読む組み合わせの数です。選ぶ順序を無視したときのr個の選び方で、ABCとCBAは1通りと数えます

P(n, r)

順列の数です。r個を選んでから並べる方法の数で、ABCとCBAは別の結果になります。いつも組み合わせの数にr!を掛けたものになります

何通りあるかが本題のときに使います。確率を式ではなく数え上げで求める場面のほとんどがこれにあたります。カードの手札、宝くじの抽選、委員会の選出、席順はどれもこの計算で、どれに取りかかる前にも必ず決めておかなければならないことが1つあります。順序を数えるかどうかです。ポーカーの手札は組み合わせで、表彰台の並びは順列になります。重複のスイッチが効くのは、同じ選択を2度できる場合です。味のメニューから3スクープを選ぶとき、順序はやはり問題になりませんが味は重複してよいので、これは普通の組み合わせではなく重複を許す組み合わせの数になります。このページは確率そのものではなく、確率が組み立てられるもとになる数だけを計算します。

1. 10個から3個選ぶ：組み合わせ120通り、順列720通り

   1. 順序を無視すると、C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120
   2. 順序を数えると、P(10, 3) = 10 × 9 × 8 = 720
   3. 両者は3! = 6だけ違い、これは選んだ3個を並べる方法の数です
   4. 検算：120 × 6 = 720

   この2つを区別しておくことこそが、このページの存在理由です。同じ3つの項目に組み合わせは1通り、順列は6通りあります。どちらか言わずに引用した数は、ここでは6倍ずれます。5個選ぶときは120倍で、そこからは小さすぎて気づけない違いではなくなります。覚えておく価値があるのは最後のステップです。順列の数はいつも組み合わせの数にr!を掛けたもので、順序を無視した選び方がどれもちょうどr!通りに並べられるからです。

2. 同じ10個と3個で、重複を許す場合

   1. 重複を許し、順序を無視すると、C = (10 + 3 − 1)! / (3! × 9!) = C(12, 3) = 220
   2. 重複を許し、順序を数えると、P = 10³ = 1,000
   3. 組み合わせのほうは母集団が実質的に大きくなります。式がnにr − 1を足すからです。一方、順列の数は各枠で1つずつ選ぶだけです
   4. 検算：220は120ではなく、1,000は720でもありません。スイッチを切り替えると両方の行が動きました

   両方の行が動いたことが、スイッチの細かい仕様ではなく要点です。組み合わせの数だけを調整する実装は220と720を並べて印字し、どちらももっともらしく見えながら別の規則を説明していることになります。順列の数が下降積ではなく累乗になっている点にも注意してください。重複を許すとr個の枠のどれでもn通りの選択があるので、1つずつ減る代わりにnʳになるのです。

3. 52枚のデッキから5枚のポーカーハンド

   1. 手札に順序はないので、数え方はC(52, 5) = 52! / (5! × 47!)
   2. 5つの下降する項を掛ける：52 × 51 × 50 × 49 × 48 = 311,875,200
   3. 5! = 120で割る：311,875,200 / 120 = 2,598,960
   4. 2行目は1行目の途中の値です。手札とは、順序のある配り方を並べ方の数で割ったものだ、というのはそういう意味です

   2,598,960はポーカーのあらゆる確率を割る数であり、このページで最も読まれる値です。ここでは2つの行をまとめて読む価値があります。順列の行は、5!で割る前の分子そのものだからです。5枚の手札は311,875,200通りの順序だった配り方で配られ、どの手札もそのうちの120通りを占めます。順序を無視した数が、順序を数えた数を並べ方の数で割ったものだと分かれば、2つを混同せずに済みます。

4. 6個から6個すべて取る：組み合わせ1通り、順列720通り

   1. すべて取る方法は1通りしかないので、C(6, 6) = 1
   2. 順列は6個すべての並べ方です：P(6, 6) = 6! = 720
   3. 2つの行の間の倍率は720 = 6!で、これはr = nのときのr!の規則そのものです

   r = nでは2つの行がもっとも離れ、組み合わせの行は1に潰れます。すべてを取り切ると選ぶ余地が残らないからです。これはポーカーの手札と並べて持っておくと役に立つ極端な例です。あちらでは隔たりが120倍、こちらでは720倍で、変わったのは選んだ1つが許す並べ方の数だけです。順列の行のほうが欲しかったのだとしたら、これがその間違いのもっとも大きい形です。

5. 3つの味から5スクープ：rがnより大きい場合

   1. 3つの味から5スクープ、順序を無視して重複を許す：C = C(3 + 5 − 1, 5) = C(7, 5) = 21
   2. 順序も数えると、P = 3⁵ = 243
   3. どちらも重複を許すからこそ合法です。許さない場合、3個から5個選ぶことはできず、このページは入力を拒否します

   ここがスイッチを好みではなく正しさの要件にする場合です。3個しかない母集団から5個選ぶことは、重複なしにはできません。だから重複を許さない設定ではこのページは入力をそのまま拒否し、許す設定では同じ入力がごく普通の2つの数を返します。組み合わせの行は、式がなぜ母集団にr − 1を足すのかも示しています。重複を許すと母集団は選ぶ数より1つ少ないだけ大きいものとして振る舞うので、3つの味を5回取ることは7個から5個を選ぶこととして数えられるのです。

どちらの数も、あるところまでは厳密な整数で、それを超えるとこのページは丸めずに拒否します。数は急速に大きくなり（100個から50個選ぶと30桁になります）、コンピュータの浮動小数点は16桁あたりでどの整数も厳密には保持できなくなるので、それほど大きな数は末尾の桁が誤ったまま、まったく普通に見える形で返ってきます。誰も気づかない形で誤った数を印字するより、このページは厳密な範囲を超えた数について例外を投げます。同じ拒否は、1,000個を超える母集団と負の数にも及びます。さらに2つの限界があります。このページは数えるだけで、それ以外はしません。組み合わせを列挙せず、数え上げず、1つを引く確率も計算しません。それは数えた数を全体で割ったものです。そして重複のスイッチが意味するのは1つだけ、同じ項目を2度以上取ってよいということです。デッキのようにカードが抜れるにつれて母集団が縮むかどうかは表現していません。

組み合わせと順列は何が違いますか

組み合わせは選んだ順序を無視し、順列は順序を数えます。10人から委員を3人選ぶのは組み合わせです。委員ABCとCBAは同じ委員会だからです。その3人に1位・2位・3位の賞を渡すのは順列で、割り当てが違うからです。2つの数は決して近くありません。順列の数は組み合わせの数にr!を掛けたもので、r!は選んだr個を並べる方法の数です。このページが両方の行を印字するのは、倍率を推測しなくて済むようにするためです。r = 3なら6、r = 5なら120になります。

電卓にあるnCrとは何ですか

nCrは組み合わせを求める電卓の機能です。nが母集団の大きさ、rが選ぶ数で、結果は順序を無視して選ぶ方法の数になります。このページが組み合わせの行に印字するのと同じ数です。隣のキーnPrは順序を数えた順列の数で、その下の行にあたります。どちらが欲しいかを見分ける簡単な方法は、選んだ2つを入れ替えると結果が変わるかを問うことです。変わらないなら答えはnCrです。

重複を許すと何が変わりますか

両方の式が変わり、どの入力が合法かも変わります。重複を許さないとき、順列の数は下降積（n × (n − 1) × …）で、組み合わせの数はそれをr!で割ったものです。重複を許すとき、順列の数は単にnのr乗になり、組み合わせの数は多重集合の数になって、n個からr個取る場合はC(n + r − 1, r)となります。人を引っかけるのは合法性のほうです。重複を許さないとき、rがnより大きいことはそもそもできず拒否されますが、許すときは3つの味から5スクープのように普通の要求になります。

大きな入力を答えずに拒否することがあるのはなぜですか

答えの末尾の桁が誤り、しかも誤って見えないからです。これらの数は極端に速く大きくなり（100個から50個選ぶとおよそ30桁になります）、コンピュータが計算に使う数は16桁あたりでどの整数も厳密には保持できなくなります。その線を越えると結果は、先頭は正しく見えて末尾が誤った近い数になります。数えた数を確率や報告書に使うのなら、答えが出ないより悪いものです。そこでこのページは厳密に表せない数について例外を投げます。1,000個を超える母集団や負の数について投げるのと同じ形です。

重複のスイッチは復元抽出のことですか

カードのデッキでこの言葉が意味する通りではありません。このスイッチが言うのは、同じ項目を2度以上選んでよいということだけで、独立な選択の母集団ではこれが復元抽出にあたります。カードの問題ではカードが抜れるにつれて母集団も縮み、そのことは上の数がすでに、重複なしの式にある下降積で織り込んでいます。5枚の手札はC(52, 5)であって、52の5乗ではありません。つまりこのスイッチは重複が許されるかどうかの話で、母集団が縮むことはスイッチではなく式のほうが扱います。

計算機の下に早見表がないのはなぜですか

表はパネルと食い違うしかないからです。この種のページが欲しくなる表は、縦にn、横にrを並べた格子ですが、パネルの答えは入力したnとrから計算されるので、固定された格子は同じ入力に対して違う数を示すことになります。このサイトで参考表を載せているページは、表が固定された値の集合（区分の境界や標準的な目盛り）を表すもので、入力の計算ではないものです。ここではパネルの2つの行が答えそのもので、キーを打つたびに動きます。

• Combination — 集合から順序を無視して選ぶ方法の数で、二項係数とも呼ばれ、「n choose k」と読みます — Wolfram MathWorld (United States)
• Permutation — 順序づけられた並びの要素を並べ替えたもので、与えられた大きさの集合についてその個数を数えたもの — Wolfram MathWorld (United States)
• Multichoose — 与えられた個数の記号の上で、与えられた長さの多重集合の数。このページが切り替える重複を許す組み合わせの数にあたります — Wolfram MathWorld (United States)