组合技巧

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

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

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

计数原理

加法原理

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

乘法原理

乘法原理是另一个直观结论,断言:若有甲乙两事,甲事有 种方法,乙事有 种方法,则合共有 种方法做完全部两事。

容斥原理

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

容斥原理用多个集合各自的大小,及其任何组合之的大小,表示出该些集合并集的大小。对于仅得两个集合的情况,容斥原理断言:两集合 之并 的大小,等于  大小之和,减去交集 的大小(因为该些元素重复数了两次)。

对于有 个有限集 的情况,原理断言:

 

除法原理

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

证明技巧

双射法

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

算两次

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

抽屉原理

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

特异元素法

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

母函数

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

 

递归关系

递归关系是利用数列某项 之前的其他项 定义该项。若证得数列的某条递归式,则可以已足以推导出此前未知的结论,不过一般而言,能找出通项公式则更佳。

参考文献

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