組み合わせ

数学 において、組み合わせとは、異なるメンバーを持つセットからアイテムを選択することであり、選択の順序は重要ではありません (順列とは異なります)。たとえば、リンゴ、オレンジ、ナシの 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}},}$$

これは階乗表記法を使うと次のように簡潔に表現できる。

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

となるときはいつでも。この式は、 n個の要素を持つ集合Sの各k組み合わせには、またはとなる順列が存在するという事実から導かれる。^[1]集合Sのすべてのk組み合わせの集合は、しばしば と表記される。 ${\displaystyle n\geq k\geq 0}$ ${\displaystyle k!}$ ${\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]上記の例で、ある種類の果物を2つずつ選ぶことが可能であれば、2選択がさらに3つあります。1つはリンゴ2個、1つはオレンジ2個、もう1つはナシ2個です。

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

数け-組み合わせ

5要素セットの3要素サブセット

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}$$

のために。 ${\displaystyle k>n}$

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

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

Sのすべての部分集合に対応する2 ^{n 個の}異なる項があり、各部分集合は対応する変数X _sの積を表す。ここで、すべてのX _{s を}ラベルなし変数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}{n-k}},}$$

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

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

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

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

最後の式は、 Sのすべての要素のn ! 通りの順列を考えることで直接理解できます。それぞれの順列は、最初のk個の要素を選択することでk 個の組み合わせを生成します。重複する選択は多数存在します。最初のk個の要素同士、および最後の ( n  −  k ) 個の要素同士の任意の組み合わせは、同じ組み合わせを生成します。これが式における除算の理由です。

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

$${\displaystyle {\binom {n}{k}}={\begin{cases}\displaystyle {\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\\displaystyle {\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 {\binom {52}{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}{\binom {52}{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 {\binom {n}{k}}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}$$

これにより

$${\displaystyle {\binom {52}{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}{\binom {52}{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 個のインデックス番号を追跡することです。最初のk個の組み合わせとして、{0 .. k −1}（0 から始まる）または {1 .. k }（1 から始まる）から始めます。次に、同じインデックス番号が 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]

証拠

上記のディオファントス方程式の解は、星、区切り線（バー）、さらに星、区切り線、というように表すことができます。この表現における星の総数はkで、バーの数はn - 1 です（n 個の部分に分割するには n-1 個の区切り線が必要になるため）。したがって、文字列にk個の星がある場合、 k + n - 1 個（またはn + k - 1 個）の記号（星とバー）の文字列が解に対応します。どの解も、 k + n − 1 個の位置からk 個を選んで星を配置し、残りの位置をバーで埋めることで表すことができます。たとえば、方程式（n = 4、k = 10）の解は^[14]で表すことができます。${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$

$${\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}$$

このような文字列の数は、10 個の星を 13 個の位置に配置する方法の数であり、4 つの要素を持つセットの 10 多重部分集合の数です。 ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$

7集合の3部分集合（左）と5集合の要素を含む3多重集合（右）間の単射
。これは、 であることを示しています。${\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}$

二項係数と同様に、これらの複数選択式の間にはいくつかの関係があります。例えば、 ${\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 までの数列の 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の組み合わせを効率的に選択する方法の一つは、母集団の各要素を反復処理し、各ステップで動的に変化する確率でその要素を選択することです（リザーバサンプリングを参照）。もう一つの方法は、 未満の非負の整数をランダムに選び、組み合わせ数システムを用いて組み合わせに変換することです。 ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ ${\displaystyle \textstyle {\binom {n}{k}}}$

物体をビンに入れる方法の数

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

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

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

この式が成り立つ理由を理解する一つの方法は、まずオブジェクトに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}}={\binom {n}{k,n-k}}={\frac {n!}{k!(n-k)!}}.}$$

参照

• 数学ポータル

• 二項係数
• 組合せ論
• ブロックデザイン
• クネザーグラフ
• 順列トピックのリスト
• マルチセット
• 確率

注記

1. ライヒル、リンダ・E. (2016). 「2.2. 微視的状態の計数」.統計物理学の現代講座. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0。
2. マズール 2010、10ページ
3. 順序なし選択とも呼ばれる。
4. 「組み合わせ」という用語が使用される場合（Brualdi 2010 のように）、セットについて議論されているのか、マルチセットについて議論されているのかを明確にするように注意する必要があります。
5. ウスペンスキー 1937年、18ページ
6. 『高校全日制教科書（必修）数学II B（中国語）（第2版）』中国人民教育出版社、2006年6月、  107～ 116頁。ISBN 978-7-107-19616-4。
7. 人教版高中数学选修2-3 [高等学校用の数学教科書、第2-3巻、People's Education Press ]。人民教育出版局。 p. 21. 2023年4月7日時点のオリジナルよりアーカイブ。
8. マズール 2010、21ページ
9. Lucia Moura. 「Generating Elementary Combinatorial Objects」（PDF） . Site.uottawa.ca . 2022年10月9日時点のオリジナルよりアーカイブ（PDF） . 2017年4月10日閲覧。
10. 「部分集合 - 組合せ論」Sagemath.org . 2017年4月10日閲覧。
11. ブルアルディ 2010、52ページ
12. ベンジャミン＆クイン 2003、70ページ
13. 記事「星と棒（組み合わせ論）」では、 nとkの役割が逆になっています。
14. ベンジャミン＆クイン 2003、71～72ページ
15. ベンジャミン＆クイン 2003, p. 72 (同一性 145)
16. ベンジャミン＆クイン 2003、71ページ
17. Mazur 2010、p. 10 星とバーは2進数で書かれており、星 = 0、バー = 1。

参考文献

• ベンジャミン、アーサー・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年）、数学的確率入門、マグロウヒル

外部リンク

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