组合技巧

证明组合学的结论时，常用到组合技巧。

一类是计数原理，如加法原理、乘法原理、容斥原理，常用于解决组合计数问题。另一类则是证明技巧，如双射法用于证明某两类物件的数目一样多，而抽屉原理则能保证某些物件存在，也用作确定离散物件数目的最大或最小值，还有算两次和特异元素法能证明许多组合恒等式。

母函数和递归关系也是很强的工具，能巧妙操作数列，描述许多组合问题的情景，甚至将之解决。

计数原理

加法原理

主条目：加法原理

加法原理是以下直观结论：若有两类方法做某事，甲类$a$种，乙类$b$种，且只能用其中一类的一种，则做该事的方法，合共$a+b$种。用较严谨的语言，两个不交集的基数之和，等于其并集的基数。

乘法原理

主条目：乘法原理

乘法原理是另一个直观结论，断言：若有甲乙两事，甲事有$a$种方法，乙事有$b$种方法，则合共有$a\cdot b$种方法做完全部两事。

容斥原理

三个集合两两相交的文氏图

主条目：容斥原理

容斥原理用多个集合各自的大小，及其任何组合之交的大小，表示出该些集合并集的大小。对于仅得两个集合的情况，容斥原理断言：两集合$A,B$之并$A\cup B$的大小，等于$A$与$B$大小之和，减去交集$A\cap B$的大小（因为该些元素重复数了两次）。

对于有$n$个有限集$A_{1},A_{2},\ldots ,A_{n}$的情况，原理断言：

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

除法原理

主条目：除法原理

除法原理讲述，若有一事要用某辅助程序就能完成，而有$n$种方式做该辅助程序，但对于原来的事而言，每种解决方法对应辅助程序的$d$种方法，则原来的事合共有$n/d$种方法。

证明技巧

双射法

主条目：双射法

要证明两类物件数量相等时，可以用双射法，即构造两类物件的集合之间的双射（一一对应关系）。

算两次

主条目：算两次

算两次是证明恒等式的技巧，方法是分别证明左右两式各自数算同一个集合的元素个数。

抽屉原理

主条目：抽屉原理

抽屉原理断言，若$a$件物放入$b$个抽屉，而$a>b$，则必有某抽屉内放有多于一件物。此原理广泛用于存在性证明，即证明具某组合性质的物件存在，但不举出例子。

特异元素法

主条目：特异元素法

特异元素法是刻意将集合中的某元素与其他元素区分，视为特殊，于是所有子集可以分为包含该特殊元素与不包含该特殊元素两类。如此，有时能化简问题。

母函数

主条目：母函数

母函数是形式幂级数（类似于多项式，但可以有无穷多个项），其系数依次对应数列的各项。以母函数表示数列，开拓了证明恒等式和求数列通项公式的新方法。数列$(a_{n})$的（一般）母函数$G$由下式定义：

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

递归关系

主条目：递归关系

递归关系是利用数列某项$a_{n}$之前的其他项$a_{i}(0\leq i\leq n-1)$定义该项。若证得数列的某条递归式，则可以已足以推导出此前未知的结论，不过一般而言，能找出通项公式则更佳。

参考文献

• van Lint, J.H.; Wilson, R.M. A Course in Combinatorics 2nd. Cambridge University Press. 2001. ISBN 0-521-00601-5.