证明组合学的结论时,常用到组合技巧。
一类是计数原理,如加法原理、乘法原理、容斥原理,常用于解决组合计数问题。另一类则是证明技巧,如双射法用于证明某两类物件的数目一样多,而抽屉原理则能保证某些物件存在,也用作确定离散物件数目的最大或最小值,还有算两次和特异元素法能证明许多组合恒等式。
母函数和递归关系也是很强的工具,能巧妙操作数列,描述许多组合问题的情景,甚至将之解决。
计数原理
加法原理
加法原理是以下直观结论:若有两类方法做某事,甲类
种,乙类
种,且只能用其中一类的一种,则做该事的方法,合共
种。用较严谨的语言,两个不交集的基数之和,等于其并集的基数。
乘法原理
乘法原理是另一个直观结论,断言:若有甲乙两事,甲事有
种方法,乙事有
种方法,则合共有
种方法做完全部两事。
容斥原理
三个集合两两相交的文氏图
容斥原理用多个集合各自的大小,及其任何组合之交的大小,表示出该些集合并集的大小。对于仅得两个集合的情况,容斥原理断言:两集合
之并
的大小,等于
与
大小之和,减去交集
的大小(因为该些元素重复数了两次)。
对于有
个有限集
的情况,原理断言:
![{\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)
递归关系
递归关系是利用数列某项
之前的其他项
定义该项。若证得数列的某条递归式,则可以已足以推导出此前未知的结论,不过一般而言,能找出通项公式则更佳。
参考文献