組み合わせ

数学において、組み合わせとは、異なるメンバーを持つ集合からアイテムを選択することであり、選択の順序は重要ではありません (順列とは異なります)。たとえば、リンゴ、オレンジ、ナシの 3 つの果物があるとします。この集合から 2 つを選ぶ組み合わせは、リンゴとナシ、リンゴとオレンジ、ナシとオレンジの 3 つがあります。より正式には、集合Sのk組み合わせは、 Sのkつの異なる要素の部分集合です。したがって、2 つの組み合わせが同一であるためには、各組み合わせに同じメンバーが含まれている必要があります (各集合内のメンバーの配置は重要ではありません)。集合にn個の要素がある場合、またはで表されるk組み合わせの数は、二項係数に等しくなります。${\displaystyle C(n,k)}$${\displaystyle C_{k}^{n}}$

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}$$

これは階乗を使って のときはいつでもと表すことができ、 のときは 0 になります。この公式は、 n個の要素を持つ集合 S の各 k 組み合わせに または のような順列が存在するという事実から導き出されます。[ ^1]集合Sのすべてのk組み合わせの集合は、 と表記されることが多いです。 ${\displaystyle \textstyle {\frac {n!}{k!(nk)!}}}$${\displaystyle k\leq n}$${\displaystyle k>n}$${\displaystyle 1!}$${\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}$${\displaystyle C_{k}^{n}=P_{k}^{n}/k!}$${\displaystyle \textstyle {\binom {S}{k}}}$

組み合わせとは、 n個のものをk 個ずつ繰り返しなく組み合わせたものである。繰り返しが許される組み合わせを指すために、繰り返しのあるk組み合わせ、k多重集合、[ ^2]またはk選択、^[3]という用語がよく使用される。^[4]上記の例で、任意の 1 種類の果物を 2 つ取ることが可能であれば、2 選択がさらに 3 つ存在することになる。1 つはリンゴ 2 個、1 つはオレンジ 2 個、1 つは梨 2 個である。

3 つの果物のセットは、組み合わせの完全なリストを書くのに十分小さいですが、セットのサイズが大きくなるにつれて、これは非現実的になります。たとえば、ポーカーのハンドは、  52 枚のカード デッキ ( n = 52) からの5 つの組み合わせ ( k = 5) として説明 できます。ハンドの 5 枚のカードはすべて異なっており、ハンド内のカードの順序は重要ではありません。このような組み合わせは 2,598,960 あり、ランダムに 1 つのハンドを引く確率は 1 / 2,598,960 です。

n個の要素からなる集合Sからk 個の組み合わせがいくつあるかは、初等的な組合せ論のテキストでは 、あるいは、 、、などの変形で表記されることが多い。 ^[5]（最後の形式はフランス語、ルーマニア語、ロシア語、中国語のテキストでは標準的である）。^{[6] [7]} しかし、同じ数は他の多くの数学の文脈でも登場し、（「nからk を選ぶ」と読むことが多い） で表記される。特に、二項式の係数として現れるため、二項係数と呼ばれる。すべての自然数kに対して、関係式によって一度に 定義することができる。${\displaystyle C(n,k)}$${\displaystyle C_{k}^{n}}$${\displaystyle {}_{n}C_{k}}$${\displaystyle {}^{n}C_{k}}$${\displaystyle C_{n,k}}$${\displaystyle C_{n}^{k}}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {n}{k}}}$

$${\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}$$

そこから明らかなのは

$${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}$$

そしてさらに

$${\displaystyle {\binom {n}{k}}=0}$$

k  >  nの場合。

これらの係数がSからのk通りの組み合わせを数えることを確認するには、まずSの要素sでラベル付けされたn個の異なる変数X _sの集合を考え、その積をSのすべての要素に 展開します。

$${\displaystyle \prod _{s\in S}(1+X_{s});}$$

Sのすべての部分集合に対応する2 ^{n 個の}異なる項があり、各部分集合は対応する変数Xの積を与えます。ここで、すべてのX_をラベルなし変数Xに等しく設定して、積_が(1 + X ) ⁿになるようにすると、 Sの各k組み合わせの項はX ^kになり、結果のその累乗の係数は、そのようなk組み合わせの数に等しくなります。

二項係数は様々な方法で明示的に計算できる。(1 + X ) ⁿまでの展開に対して二項係数をすべて得るには、（既に述べた基本的なケースに加えて）再帰関係を使うことができる。

$${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$$

0 < k < nの場合、これは(1 + X ) ⁿ = (1 + X ) ^{n − 1} (1 + X )から得られ、パスカルの三角形の構築につながります。

個々の二項係数を決定するには、次の式を使用する方が実用的である。

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}$$

分子はnのk順列、つまりSのk個の異なる要素のシーケンスの数を示します。一方、分母は、順序を無視した場合に 同じk組み合わせを与えるようなk順列の数を示します。

kがn /2を超える場合、上記の式には分子と分母に共通の因数が含まれており、それらを打ち消すと次の関係が得られます。

$${\displaystyle {\binom {n}{k}}={\binom {n}{nk}},}$$

0 ≤ k ≤ nの場合。これは二項式から明らかな対称性を表しており、そのような組み合わせの補数、つまり( n − k )組み合わせを取ることでk組み合わせの観点からも理解できます。

最後に、この対称性を直接示す式があり、これは覚えやすいという利点があります。

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(nk)!}},}$$

ここで、n ! はnの階乗を表します。これは、前の式で分母と分子に( n − k ) !を掛けて得られるため、計算効率は前の式よりも確かに低くなります。

最後の式は、 Sのすべての要素のn ! 順列を考慮することで直接理解できます。各順列では、最初のk個の要素を選択することでk の組み合わせが得られます。重複する選択は多数あります。最初のk個の要素同士の順列と、最後の ( n  −  k ) 個の要素同士の順列の組み合わせはすべて同じ組み合わせになります。これが式の除算を説明しています。

上記の式から、パスカルの三角形の 3 つの方向すべてにおける隣接する数値間の関係がわかります。

$${\displaystyle {\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{nk}}&\quad {\text{if }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}$$

基本的なケースと組み合わせることで、同じ集合（パスカルの三角形の行）からのすべての組み合わせ、成長するサイズの集合のk組み合わせ、固定サイズn − kの補集合を持つ組み合わせをそれぞれ連続的に計算することができます。 ${\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}$

具体的な例として、標準的な52枚のカードデッキから5枚のカードのハンドの数を計算すると次のようになります。^[8]

$${\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}$$

あるいは、階乗の観点で式を使用し、分子の因数を分母の因数の一部で打ち消し、残りの因数を掛け合わせるだけで済む場合もあります。 $${\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}$$

もう一つの代替計算法は、最初の計算法と同等で、次のように記述する。

$${\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}$$

これにより

$${\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}$$

52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5の順序で評価すると、整数演算のみを使用して計算できます。その理由は、各除算が発生すると、生成される中間結果自体が二項係数であるため、剰余が発生しないからです。

簡略化を行わずに階乗に関して対称式を使用すると、かなり大規模な計算になります。

$${\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}$$

n個の要素を持つ与えられた集合Sのすべてのk組み合わせを、ある決まった順序で列挙することができます。これにより、整数の区間からそれらのk組み合わせの集合への一対一の関係が確立されます。S自体が順序付けられていると仮定すると、たとえばS = { 1, 2, ..., n }、そのk組み合わせを順序付ける自然な方法は 2 つあります。1 つは最小の要素を最初に比較する方法 (上の図のように)、もう 1 つは最大の要素を最初に比較する方法です。後者のオプションには、新しい最大要素をSに追加しても列挙の最初の部分は変更されず、より大きな集合の新しいk組み合わせが以前の組み合わせの後に追加されるだけであるという利点があります。このプロセスを繰り返すと、列挙をさらに大きな集合のk組み合わせで無制限に拡張できます。さらに、整数の区間を 0 から開始すると、列挙内の特定の場所iでのk組み合わせはiから簡単に計算でき、このようにして得られた一対一の関係は組み合わせ数システムと呼ばれます。計算数学では「ランク」/「ランキング」および「アンランキング」としても知られています。^{[9] [10]}${\displaystyle {\tbinom {n}{k}}}$

kの組み合わせを列挙する方法は多数あります。1 つの方法は、最初に許可される k の組み合わせとして {0 .. k −1} (0 から始まる) または {1 .. k } (1 から始まる)から始めて、選択された要素のkインデックス番号を追跡することです。次に、2 つの同じインデックス番号が作成されない最小のインデックス番号を増分して、次の許可されるk の組み合わせに繰り返し移動し、同時にすべての小さいインデックス番号を初期値にリセットします。

繰り返しのあるk個の組み合わせ、またはk個の組み合わせ、またはサイズnの集合Sからのサイズkの多重部分集合は、順序は考慮されない、必ずしも異なるとは限らないSのk 個の要素のセットによって与えられます。2 つのシーケンスは、項を並べ替えることで一方を他方から取得できる場合、同じ多重集合を定義します。言い換えると、これは重複 (つまり、置き換え) を許容するが順序の違いを無視する (例: {2,1,2} = {1,2,2})、 n個の要素のセットからのk個の要素のサンプルです。Sの各要素にインデックスを関連付け、 Sの要素をオブジェクトの型と考えると、多重部分集合内の型iの要素の数を で表すことができます。サイズkの多重部分集合の数は、ディオファントス方程式の非負の整数 (つまり、ゼロを許容する) 解の数です。^[11]${\displaystyle x_{i}}$

$${\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}$$

Sがn個の要素を持つ場合、そのようなk多重部分集合の数は次のように表される。

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}$$

これはk個の部分集合を数える二項係数に類似した表記法である。この表現n multichoose k ^[12]は二項係数で表すこともできる。

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}$$

この関係は星と棒と呼ばれる表現を使って簡単に証明できる。^[13]

二項係数と同様に、これらの複数選択式の間にはいくつかの関係があります。たとえば、 ${\displaystyle n\geq 1,k\geq 0}$

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}$$ この同一性は、上記の表現における星とバーを入れ替えることによって得られる。^[15]

例えば、 メニューに4種類のドーナツ（ n = 4）があり、3種類のドーナツ（ k  = 3）が欲しい場合、繰り返してドーナツを選ぶ方法の数は次のように計算できます。

$${\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}$$

この結果は、集合S = {1,2,3,4}の 3 多重集合をすべてリストすることで確認できます。これは次の表に示されています。^[16] 2 列目には実際に選択したドーナツがリストされ、3 列目には方程式の非負整数解が示され、最後の列には解の星とバーの表現が示されています。^[17]${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$

すべてのkに対するkの組み合わせの数は、 n個の要素からなる集合の部分集合の数です。この数が 2 ⁿであることを示す方法はいくつかあります。組み合わせに関して言えば、はパスカルの三角形の二項係数のn行目 (0 から数えて)の合計です。これらの組み合わせ (部分集合) は、 0 から 2 ⁿ − 1 まで数えた2 進数の集合の 1 桁目によって列挙されます。ここで、各桁の位置はn 個 の集合からの項目です。 ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$

1 から 3 までの番号が付けられた 3 枚のカードがある場合、空集合を含む 8 つの異なる組み合わせ (サブセット)が存在します。

$${\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}$$

これらのサブセットを（同じ順序で）2 進数の数字で表すと次のようになります。

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111

特定のセットまたはリストからランダムな組み合わせを選択するためのアルゴリズムはさまざまあります。サンプル サイズが大きい場合、拒否サンプリングは非常に遅くなります。 サイズnの母集団からk の組み合わせを効率的に選択する方法の 1 つは、母集団の各要素を反復処理し、各ステップで動的に変化する確率でその要素を選択することです(リザーバ サンプリングを参照)。 もう 1 つの方法は、 未満の負でない整数をランダムに選択し、組み合わせ数システムを使用して組み合わせに変換することです。 ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$${\displaystyle \textstyle {\binom {n}{k}}}$

組み合わせは、 2つのアイテムセットの選択と考えることもできます。選択されたビンに入るアイテムと選択されなかったビンに入るアイテムです。これは、すべてのアイテムが正確に1つのビンに入るという制約の下で、任意の数のビンに一般化できます。オブジェクトをビンに入れる方法の数は、多項式係数によって与えられます。

$${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}$$

ここで、nはアイテムの数、mはビンの数、 はビンiに入るアイテムの数です。 ${\displaystyle k_{i}}$

この等式が成り立つ理由を確認する 1 つの方法は、まずオブジェクトに1からnまで任意に番号を付け、番号の付いたオブジェクトを順番に最初のビンに入れ、番号の付いたオブジェクトを順番に 2 番目のビンに入れる、というようにすることです。番号付けにはさまざまな方法がありますが、その多くは同等です。ビン内のアイテムのセットだけが重要であり、ビン内の順序は重要ではないためです。各ビンの内容を組み合わせた順列はすべて、アイテムをビンに入れる同等の方法を生み出します。その結果、すべての同値クラスはさまざまな番号付けで構成され、同値クラスの数は になります。 ${\displaystyle 1,2,\ldots ,k_{1}}$${\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}$${\displaystyle n!}$${\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}$${\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}$

二項係数は、k個の項目が選択されたビンに入り、残りの項目が選択されていないビンに入る特殊なケースです。 ${\displaystyle n-k}$

$${\displaystyle {\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.}$$

• ベンジャミン、アーサー・T. ;クイン、ジェニファー・J. (2003)、「本当に重要な証明：組み合わせ証明の技術」、ドルチアーニ数学解説集 27、アメリカ数学協会、ISBN 978-0-88385-333-7
• Brualdi, Richard A. (2010)、Introductory Combinatorics (第 5 版)、Pearson Prentice Hall、ISBN 978-0-13-602040-0
• Erwin Kreyszig、「Advanced Engineering Mathematics」、John Wiley & Sons、INC、1999年。
• マズール、デイビッド・R（2010）、組合せ論：ガイドツアー、アメリカ数学協会、ISBN 978-0-88385-762-5
• ライザー、ハーバート・ジョン（1963）、組合せ数学、カーラス数学モノグラフ14、アメリカ数学協会
• ウスペンスキー、ジェームズ（1937）、数学的確率入門、マグロウヒル

• 組み合わせ論に関する Topcoder チュートリアル
• 一般的な順列と組み合わせの数学の問題の多くと詳細な解答
• 選択肢が繰り返され、順序が重要ではない組み合わせの未知の公式
• 与えられた合計を持つサイコロを振る問題 繰り返しのある組み合わせを複数のサイコロを振ることに適用する