与えられたn要素の集合Sからのk組合せの数は初等組合せ論ではしばしばC ( n , k ) {displaystyle C(n,k)} で表される。
、またはC k n {displaystyle C_{k}^{n}} のようなバリエーションで表現される。
, n C k {}_displaystyle {}_{n}C_{k}}.
, n C k {displaystyle {}^{n}C_{k}}.
, C n , k {displaystyle C_{n,k}} …
あるいは C n k {displaystyle C_{n}^{k}} でもよい。
(後者はフランス語、ルーマニア語、ロシア語、中国語、ポーランド語のテキストで標準的に使われている)。 しかし、同じ数が他の多くの数学的文脈で登場し、( n k ) {displaystyle {tbinom {n}{k}}} で示される。
（「n choose k」と読むことが多い）。特に二項式の係数として使われることから、二項係数と呼ばれるようになった。 ( n k ) {displaystyle { {tbinom {n}{k}}} を定義することができます。
すべての自然数kについて、( 1 + X ) n = ∑ k ≧ 0 ( n k ) X k , {displaystyle (1+X)^{n}=sum _{k}{binom {n}{k}}X^{k} の関係で一度に計算される。}
ここから、
( n 0 ) = ( n n ) = 1 , {displaystyle {}={binom {n}{n}}=1,}
さらに、 ( n k ) = 0 {displaystyle {binom {n}{k}=0} は明らかである。
for k > n.
これらの係数がSからのk組を数えることを見るには、まずSの要素sでラベル付けされたn個の異なる変数Xsのコレクションを考え、Sの全ての要素にわたって積を展開します：
∏ s∈S ( 1 + X s ) ; {displaystyle \prod _{sin S}(1+X_{s});} ｝。
これはSのすべての部分集合に対応する2n個の異なる項を持ち、それぞれの部分集合は対応する変数Xsの積を与える。 ここでXsをすべてラベルのない変数Xと等しくして、積が(1 + X)nとなるように、Sからの各k組合せの項はXkとなり、結果におけるその冪の係数はそのようなk組合せの数に等しくなる
二項係数は様々な方法で明示的に計算することができる。 (1 + X)n までの展開についてそれらのすべてを得るには、(すでに与えられた基本的なケースに加えて) 再帰関係
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) を使用することができます。 表示スタイル {{binom {n}{k}}={{binom {n-1}{k-1}}+{binom {n-1}{k}},}
for 0 < n, (1 + X)n = (1 + X)n – 1(1 + X) から成り立ちます。 となり、パスカルの三角形が構成される。
個々の二項係数を求めるには、
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k という公式を使う方がより実用的です ! {displaystyle {binom {n}{k}}={frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}} となります。
.
分子はnのk-permutationsの数を与える、すなわち, のk-permutationの数を与え、分母は順序を無視したときに同じk-combinationを与えるそのようなk-permutationの数を与える。
kがn/2を超えるとき、上式は分子と分母に共通の因子を含み、それらを打ち消すと
( n k ) = ( n n – k ) , {displaystyle {}={binom {n}{n-k}},}
0≦k≦nの関係式を得ます。 これは二項式から明らかな対称性を表しており、またk-組合せについても、その補数である(n – k)-組合せをとることで理解できる。
最後に、この対称性を直接示す式があり、覚えやすいというメリットがある：
( n k ) = n ! ( n – k ) ! ここでn!はnの階乗を表し、分母と分子に(n – k)を掛けて前の式から得られる!
最後の式はSの全要素の並べ換えをn！個考えることで直接理解することができる。 最初のk個の要素同士、最後の(n – k)個の要素同士の順列を組み合わせると同じ組み合わせになるため、式中の分割が説明できる。
以上の式から、パスカルの三角形の3方向で隣り合う数同士の関係が導かれる。
( n k ) = { ( n k – 1 ) n – k + 1 k if k > 0 ( n – 1 k ) n n – k if k < n ( n – 1 k – 1 ) n k if n , k > 0 {displaystyle {binom {n}{k}}={{begin{cases}{binom {n}{k-1}}{frac {n-k+1}}}&quad {text{if }}k>0 {binom {n->{k1}{k}}{frac {n}{n-k}}&quad {text{if }}k<n}{binom {n-1}{k-1}}{frac {n}{k}}&quad {text{if }}n.B.C.C.C.C.C.C.C.C.C.C.C.C.C.C.C.C,k>0\end{cases}}}
.
Together with basic cases ( n 0 ) = 1 = ( n n ) {displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}} 。
, これらはそれぞれ、同じ集合（パスカルの三角形の一行）からの組み合わせの全数、大きくなる集合のk-組み合わせ、固定サイズn – kの補数を持つ組み合わせの連続計算を可能にするものです。
組み合わせの数え方の例編集
具体的な例として、標準的な52枚の山札から可能な5枚の手札の数を次のように計算できる：
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311,875,200 120 = 2,598,960. 52 5}={frac {52times 51times 50times 49times 48}{5times 4times 3times 2times 1}}={frac {311{, }875{, }200}{120}}=2{, }598{, }960.}} {displaystyle {52 ↘ 5}={frac {52times 51times 50times 49times 48}}={5}}とする。
あるいは、階乗の公式を使い、分子の因子を分母の因子の一部と相殺し、残りの因子の掛け算だけが必要です：
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. displaystyle {begin{alignedat}{2}{52 \choose 5}&={frac {52times 51times 50times 49times 48times {cancel {47!}}{5times 4times 3times 2times {cancel {1}} {cancel {47!}}} {frac{51times 52}{5!}}={47!}}={5displaystyle {big{52!}} {frac {52Times 51Times 50Times 48Times}{5!47!}} {cancel {47!}}{5displaystyle {2}{52times 51Times 51Times 51Times 49Times 52Times 52Times}={52displaystyle 52}
最初の計算と同じように、
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 ×⋯ × ( n – ( k – 1 ) k と書くこともできます。 {displaystyle {n \choose k}={frac {(n-0)}{1}}times {frac {(n-1)}{2}}times {frac {(n-2)}{3}}times {frac {(n-(k-1))}{k}}},}
となり、
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598 となります。960 {displaystyle {52 \choose 5}={{frac {52}{1}}}times {frac {51}{2}}}times {frac {50}{3}}} {frac {49}{4}}times {frac {48}{5}}=2{,}598{,}960}} {displaystyle{52}}は、以下の通りです。
.
52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 の順に評価すると、整数演算だけで計算できることになる。 5811>
簡略化せずに階乗で対称式を用いると、かなり大掛かりな計算ができます。 ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {52 \choose 5}&={frac {n!}{k!(n-k)!}}={frac {52!}{5!(52-5)!}}={frac {52!}{5!!! 47!!}}\\&={\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}}\\&=2{,}598{,}960.\ʕ-̫͡-ʔ
Enumerating k-combinationsEdit
与えられたn個の要素の集合Sについて、ある一定の順序ですべてのk組を列挙でき、これにより( n k ){displaystyle {tbinom {n}{k}} の区間から双射が確立される。｝
整数で、それらのk組合せの集合である。 Sがそれ自身順序付けされていると仮定すると、例えばS = { 1, 2, …, n }のように、そのk-組合せの順序付けには二つの自然な可能性がある：（上の図のように）それらの最小の要素を最初に比較すること、またはそれらの最大の要素を最初に比較することである。 後者は、Sに新しい最大要素を追加しても、列挙の最初の部分は変更されず、大きい集合の新しいk-組合せが前のものの後に追加されるだけという利点がある。 これを繰り返すと、より大きな集合のk組合せで無限に列挙を拡張することができる。 さらに、整数の区間を0から始めるとすると、列挙の任意の場所iにおけるk組合せは、iから容易に計算することができ、このようにして得られた両対称は、組合せ数系として知られている。 また、計算数学では「ランク」/「順位」/「アンランキング」とも呼ばれる。
k個の組合せを列挙する方法はたくさんある。 1つの方法は2n未満の2進数を全て訪ねることである。 k個の非ゼロビットを持つ数字を選ぶが、これは小さなnでも非常に効率が悪い（例えば、n=20では約100万個の数字を訪問する必要があるが、k個の組み合わせの最大許容数はk=10で約18万6000個である）。 このような数におけるこれらの1ビットの位置は、集合{ 1, …, n }の特定のk組合せである。 もう一つの簡単で高速な方法は、選択された要素のインデックス番号を{0 … k-1}からk個追跡することです。 (ゼロベース)または{1 … k}を使用します。 (1ベース)を最初の許容されるk組合せとし、最後のインデックス番号がn-1 (0ベース)またはn (1ベース)より小さい場合、またはそれに続くインデックス番号から1を引いたものより小さい最後のインデックス番号xが存在すればそれを増分し、x以降のインデックス番号を{x+1、x+2、・・・}に再設定して繰り返し次の許容されるk組合せへ移動します..
…。