本条目存在以下问题,请协助 改善本条目或在 讨论页针对议题发表看法。
此条目需要补充更多来源。 (2021年10月15日) 请协助补充多方面可靠来源以改善这篇条目,无法查证的内容可能会因为异议提出而移除。 致使用者:请搜索一下条目的标题(来源搜索:"组合技巧" — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 |
|
证明组合学的结论时,常用到组合技巧。
一类是计数原理,如加法原理、乘法原理、容斥原理,常用于解决组合计数问题。另一类则是证明技巧,如双射法用于证明某两类物件的数目一样多,而抽屉原理则能保证某些物件存在,也用作确定离散物件数目的最大或最小值,还有算两次和特异元素法能证明许多组合恒等式。
母函数和递归关系也是很强的工具,能巧妙操作数列,描述许多组合问题的情景,甚至将之解决。
计数原理
加法原理
加法原理是以下直观结论:若有两类方法做某事,甲类 种,乙类 种,且只能用其中一类的一种,则做该事的方法,合共 种。用较严谨的语言,两个不交集的基数之和,等于其并集的基数。
乘法原理
乘法原理是另一个直观结论,断言:若有甲乙两事,甲事有 种方法,乙事有 种方法,则合共有 种方法做完全部两事。
容斥原理
主条目:容斥原理
容斥原理用多个集合各自的大小,及其任何组合之交的大小,表示出该些集合并集的大小。对于仅得两个集合的情况,容斥原理断言:两集合 之并 的大小,等于 与 大小之和,减去交集 的大小(因为该些元素重复数了两次)。
对于有 个有限集 的情况,原理断言:
-
除法原理
主条目:除法原理
除法原理讲述,若有一事要用某辅助程序就能完成,而有 种方式做该辅助程序,但对于原来的事而言,每种解决方法对应辅助程序的 种方法,则原来的事合共有 种方法。
证明技巧
双射法
要证明两类物件数量相等时,可以用双射法,即构造两类物件的集合之间的双射(一一对应关系)。
算两次
算两次是证明恒等式的技巧,方法是分别证明左右两式各自数算同一个集合的元素个数。
抽屉原理
主条目:抽屉原理
抽屉原理断言,若 件物放入 个抽屉,而 ,则必有某抽屉内放有多于一件物。此原理广泛用于存在性证明,即证明具某组合性质的物件存在,但不举出例子。
特异元素法
主条目:特异元素法
特异元素法是刻意将集合中的某元素与其他元素区分,视为特殊,于是所有子集可以分为包含该特殊元素与不包含该特殊元素两类。如此,有时能化简问题。
母函数
母函数是形式幂级数(类似于多项式,但可以有无穷多个项),其系数依次对应数列的各项。以母函数表示数列,开拓了证明恒等式和求数列通项公式的新方法。数列 的(一般)母函数 由下式定义:
-
递归关系
主条目:递归关系
递归关系是利用数列某项 之前的其他项 定义该项。若证得数列的某条递归式,则可以已足以推导出此前未知的结论,不过一般而言,能找出通项公式则更佳。
参考文献
- van Lint, J.H.; Wilson, R.M. A Course in Combinatorics 2nd. Cambridge University Press. 2001. ISBN 0-521-00601-5.