組合技巧

證明組合學的結論時,常用到組合技巧

一類是計數原理,如加法原理乘法原理容斥原理,常用於解決組合計數問題。另一類則是證明技巧,如双射法用於證明某兩類物件的數目一樣多,而抽屜原理則能保證某些物件存在,也用作確定離散物件數目的最大或最小值,還有算兩次特異元素法能證明許多組合恆等式

母函数遞歸關係也是很強的工具,能巧妙操作數列,描述許多組合問題的情景,甚至將之解決。

計數原理

加法原理

加法原理是以下直觀結論:若有兩類方法做某事,甲類種,乙類種,且只能用其中一類的一種,則做該事的方法,合共種。用較嚴謹的語言,兩個不交集基數之和,等於其並集的基數。

乘法原理

乘法原理是另一個直觀結論,斷言:若有甲乙兩事,甲事有種方法,乙事有種方法,則合共有種方法做完全部兩事。

容斥原理

三個集合兩兩相交的文氏圖

容斥原理用多個集合各自的大小,及其任何組合之的大小,表示出該些集合並集的大小。對於僅得兩個集合的情況,容斥原理斷言:兩集合之並的大小,等於大小之和,減去交集的大小(因為該些元素重複數了兩次)。

對於有個有限集的情況,原理斷言:

除法原理

除法原理講述,若有一事要用某輔助程序就能完成,而有種方式做該輔助程序,但對於原來的事而言,每種解決方法對應輔助程序的種方法,則原來的事合共有種方法。

證明技巧

雙射法

要證明兩類物件數量相等時,可以用雙射法,即構造兩類物件的集合之間的双射(一一對應關係)。

算兩次

算兩次是證明恆等式的技巧,方法是分別證明左右兩式各自數算同一個集合的元素個數。

抽屜原理

抽屜原理斷言,若件物放入個抽屜,而,則必有某抽屜內放有多於一件物。此原理廣泛用於存在性證明,即證明具某組合性質的物件存在,但不舉出例子。

特異元素法

特異元素法是刻意將集合中的某元素與其他元素區分,視為特殊,於是所有子集可以分為包含該特殊元素與不包含該特殊元素兩類。如此,有時能化簡問題。

母函數

母函數是形式冪級數(類似於多項式,但可以有無窮多個項),其系數依次對應數列的各項。以母函數表示數列,開拓了證明恆等式和求數列通項公式的新方法。數列的(一般)母函數由下式定義:

遞歸關係

遞歸關係是利用數列某項之前的其他項定義該項。若證得數列的某條遞歸式,則可以已足以推導出此前未知的結論,不過一般而言,能找出通項公式則更佳。

參考文獻

  • van Lint, J.H.; Wilson, R.M. 2nd. Cambridge University Press. 2001. ISBN 0-521-00601-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.