組合技巧

Template:Multiple issues 證明組合學的結論時，常用到組合技巧。

一類是計數原理，如加法原理、乘法原理、容斥原理，常用於解決組合計數問題。另一類則是證明技巧，如双射法用於證明某兩類物件的數目一樣多，而抽屜原理則能保證某些物件存在，也用作確定離散物件數目的最大或最小值，還有算兩次和Template:Link-en能證明許多組合恆等式。

母函数和遞歸關係也是很強的工具，能巧妙操作數列，描述許多組合問題的情景，甚至將之解決。

計數原理

加法原理

加法原理是以下直觀結論：若有兩類方法做某事，甲類$a$種，乙類$b$種，且只能用其中一類的一種，則做該事的方法，合共$a+b$種。用較嚴謹的語言，兩個不交集的基數之和，等於其並集的基數。

乘法原理

乘法原理是另一個直觀結論，斷言：若有甲乙兩事，甲事有$a$種方法，乙事有$b$種方法，則合共有$a\cdot b$種方法做完全部兩事。

容斥原理

三個集合兩兩相交的文氏圖

容斥原理用多個集合各自的大小，及其任何組合之交的大小，表示出該些集合並集的大小。對於僅得兩個集合的情況，容斥原理斷言：兩集合$A,B$之並$A\cup B$的大小，等於$A$與$B$大小之和，減去交集$A\cap B$的大小（因為該些元素重複數了兩次）。

對於有$n$個有限集$A_1,A_2,\dots ,A_n$的情況，原理斷言：

$\begin{array}{cc}\left|\bigcup _{i=1}^n{A}_i\right|& =\sum _{i=1}^n\left|A_i\right|-\sum _{i,j:1\le i<j\le n}|A_i\cap A_j|\\ & +\sum _{i,j,k:1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots +{(-1)}^{n-1}|A_1\cap \cdots \cap A_n|\\ & =\sum _{\begin{array}{c}I\subseteq \{1,2,\dots ,n\}\\ I\ne \varnothing \end{array}}(-1{)}^{|I|-1}\left|\bigcap _{i\in I}{A}_i\right|.\end{array}$

除法原理

除法原理講述，若有一事要用某輔助程序就能完成，而有$n$種方式做該輔助程序，但對於原來的事而言，每種解決方法對應輔助程序的$d$種方法，則原來的事合共有$n/d$種方法。

證明技巧

雙射法

要證明兩類物件數量相等時，可以用雙射法，即構造兩類物件的集合之間的双射（一一對應關係）。

算兩次

算兩次是證明恆等式的技巧，方法是分別證明左右兩式各自數算同一個集合的元素個數。

抽屜原理

抽屜原理斷言，若$a$件物放入$b$個抽屜，而$a>b$，則必有某抽屜內放有多於一件物。此原理廣泛用於存在性證明，即證明具某組合性質的物件存在，但不舉出例子。

特異元素法

特異元素法是刻意將集合中的某元素與其他元素區分，視為特殊，於是所有子集可以分為包含該特殊元素與不包含該特殊元素兩類。如此，有時能化簡問題。

母函數

母函數是形式冪級數（類似於多項式，但可以有無窮多個項），其系數依次對應數列的各項。以母函數表示數列，開拓了證明恆等式和求數列通項公式的新方法。數列$(a_n)$的（一般）母函數$G$由下式定義：

$G(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n.$

遞歸關係

遞歸關係是利用數列某項$a_n$之前的其他項$a_i(0\le i\le n-1)$定義該項。若證得數列的某條遞歸式，則可以已足以推導出此前未知的結論，不過一般而言，能找出通項公式則更佳。

參考文獻

• Template:Cite book