組み合わせ原理

組み合わせ論における結果の証明においては、いくつかの有用な組み合わせ規則または組み合わせ原理が一般的に認識され、利用されている。

和の法則、積の法則、包含排除法則は、列挙の目的でよく用いられます。全単射証明は、2つの集合が同じ数の要素を持つことを示すために利用されます。鳩の巣原理は、何かの存在を確認したり、離散的な文脈において何かの最小数または最大数を決定するためによく用いられます。

多くの組み合わせ恒等式は、二重計数法や特定要素法から導き出される。生成関数と漸化式は、数列を操作するために使用できる強力なツールであり、多くの組み合わせ問題を解決できないまでも記述することができる。

和の法則とは、ある事象（または何かを行う方法）にa通りの可能な結果があり、別の事象（または別の何かを行う方法）にb通りの可能な結果があり、かつ、その 2 つの事象が同時に起こることはない（または、その 2 つのことが同時に行われることはない）場合、事象の可能な結果の総数はa + b通りである（または、どちらか一方のことを行う可能な方法の総数は a + b 通りである）という直感的な原理です。より厳密に言えば、互いに素な 2 つの集合の大きさの合計は、それらの和集合の大きさに等しくなります。

積の法則は、あることを行う方法がa通りあり、別のことを行う方法がb通りあるならば、両方のことを行う方法はa  · b通りあるという、もう一つの直感的な原理です。 

包含排除原理は、複数の集合の和集合の大きさ、各集合の大きさ、および集合の可能なすべての共通部分の大きさの関係を示します。最も小さな例は、2つの集合がある場合です。AとBの和集合に含まれる要素の数は、AとBに含まれる要素の数の合計から、それらの共通部分に含まれる要素の数を引いた数に等しくなります。

一般に、この原理によれば、A ₁、 …、A _nが有限集合である場合、

${\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

除法の規則によれば、ある作業をn通りの方法で実行できる手順を用いて行う場合、その作業を行う方法はn/d通りあり、任意の方法wに対して、n通りの方法のうちちょうどd通りが方法wに対応する。

全単射証明は、一方の集合から他方の集合への全単射関数（1対1対応）を見つけることによって、2つの集合が同じ数の要素を持つことを証明します。

二重カウントとは、集合のサイズを2つの異なる方法で数える2つの式を等価にする手法である。

鳩の巣原理とは、a個の項目をb個の箱（a > b）にそれぞれ入れた場合、いずれかの箱には複数の項目が含まれるという原理である。この原理を用いることで、例えば、ある集合の中に特定の性質を持つ要素が存在することを証明することができる。

特異要素法とは、ある集合の中から「特異要素」を選び出して、何らかの結果を証明する方法である。

生成関数は、係数が与えられた数列の項に対応する形式的な冪級数です。この数列の新しい表現により、特定の数列に関する恒等式や閉形式を見つけるための新しい方法が開かれます。数列a _nの（通常の）生成関数は

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$

漸化式は、数列の各項を先行する項を用いて定義する。漸化式によって数列のこれまで知られていなかった性質が明らかになる場合もあるが、一般的には数列の項を表す閉形式の式の方が望ましい。

• van Lint, JH ; Wilson, RM (2001).組合せ論入門（第2 版）. Cambridge University Press. ISBN 0-521-00601-5。