證明組合學的結論時,常用到組合技巧。
一類是計數原理,如加法原理、乘法原理、容斥原理,常用於解決組合計數問題。另一類則是證明技巧,如双射法用於證明某兩類物件的數目一樣多,而抽屜原理則能保證某些物件存在,也用作確定離散物件數目的最大或最小值,還有算兩次和特異元素法能證明許多組合恆等式。
母函数和遞歸關係也是很強的工具,能巧妙操作數列,描述許多組合問題的情景,甚至將之解決。
加法原理是以下直觀結論:若有兩類方法做某事,甲類
種,乙類
種,且只能用其中一類的一種,則做該事的方法,合共
種。用較嚴謹的語言,兩個不交集的基數之和,等於其並集的基數。
乘法原理是另一個直觀結論,斷言:若有甲乙兩事,甲事有
種方法,乙事有
種方法,則合共有
種方法做完全部兩事。
三個集合兩兩相交的文氏圖
容斥原理用多個集合各自的大小,及其任何組合之交的大小,表示出該些集合並集的大小。對於僅得兩個集合的情況,容斥原理斷言:兩集合
之並
的大小,等於
與
大小之和,減去交集
的大小(因為該些元素重複數了兩次)。
對於有
個有限集
的情況,原理斷言:
![{\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|\\&=\sum _{\begin{smallmatrix}I\subseteq \{1,2,\ldots ,n\}\\I\neq \varnothing \end{smallmatrix}}(-1)^{|I|-1}\left|\bigcap _{i\in I}A_{i}\right|.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3656c0d035ea5cc9ad30300aa32824314a66b12)
除法原理講述,若有一事要用某輔助程序就能完成,而有
種方式做該輔助程序,但對於原來的事而言,每種解決方法對應輔助程序的
種方法,則原來的事合共有
種方法。
要證明兩類物件數量相等時,可以用雙射法,即構造兩類物件的集合之間的双射(一一對應關係)。
算兩次是證明恆等式的技巧,方法是分別證明左右兩式各自數算同一個集合的元素個數。
抽屜原理斷言,若
件物放入
個抽屜,而
,則必有某抽屜內放有多於一件物。此原理廣泛用於存在性證明,即證明具某組合性質的物件存在,但不舉出例子。
特異元素法是刻意將集合中的某元素與其他元素區分,視為特殊,於是所有子集可以分為包含該特殊元素與不包含該特殊元素兩類。如此,有時能化簡問題。
母函數是形式冪級數(類似於多項式,但可以有無窮多個項),其系數依次對應數列的各項。以母函數表示數列,開拓了證明恆等式和求數列通項公式的新方法。數列
的(一般)母函數
由下式定義:
![{\displaystyle G(x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8be416a87656fa1b5bfe02aee1e956ba3d23ac7a)
遞歸關係是利用數列某項
之前的其他項
定義該項。若證得數列的某條遞歸式,則可以已足以推導出此前未知的結論,不過一般而言,能找出通項公式則更佳。