查看“︁組合技巧”︁的源代码

{{Multiple issues|
{{No footnotes|time=2021-10-15T23:10:15+00:00}}
{{Refimprove|time=2021-10-15T23:10:15+00:00}}
}}
證明[[組合學]]的結論時，常用到'''組合技巧'''。

一類是'''計數原理'''，如[[加法原理]]、[[乘法原理]]、[[容斥原理]]，常用於解決[[組合計數]]問題。另一類則是證明技巧，如[[双射法]]用於證明某兩類物件的數目[[等勢|一樣多]]，而[[鴿巢原理|抽屜原理]]則能保證某些物件存在，也用作確定[[离散数学|離散]]物件數目的最大或最小值，還有[[算兩次]]和{{link-en|特異元素法|method of distinguished element}}能證明許多[[組合恆等式]]。

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

== 計數原理 ==
=== 加法原理 ===

{{main|加法原理}}

加法原理是以下直觀結論：若有兩類方法做某事，甲類<math>a</math>種，乙類<math>b</math>種，且只能用其中一類的一種，則做該事的方法，合共<math>a+b</math>種。用較嚴謹的語言，兩個[[不交集]]的[[基數 (數學)|基數]]之和，等於其[[並集]]的基數。

=== 乘法原理 ===

{{main|乘法原理}}

乘法原理是另一個直觀結論，斷言：若有甲乙兩事，甲事有<math>a</math>種方法，乙事有<math>b</math>種方法，則合共有<math>a \cdot b</math>種方法做完全部兩事。

=== 容斥原理 ===

[[File:Inclusion-exclusion.svg|thumb|三個集合兩兩相交的[[文氏圖]]]]

{{main|容斥原理}}

容斥原理用多個集合各自的大小，及其任何組合之[[交集|交]]的大小，表示出該些集合[[並集]]的大小。對於僅得兩個集合的情況，容斥原理斷言：兩集合<math>A, B</math>之並<math>A\cup B</math>的大小，等於<math>A</math>與<math>B</math>大小之和，減去交集<math>A \cap B</math>的大小（因為該些元素重複數了兩次）。

對於有<math>n</math>個有限集<math>A_1, A_2, \ldots, A_n</math>的情況，原理斷言：

:<math>\begin{align}
\left|\bigcup_{i=1}^n A_i\right|
& {} = \sum_{i=1}^n \left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n} \left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le 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{align}</math>

=== 除法原理 ===

{{main|{{le|除法原理|Rule of division (combinatorics)}}}}

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

==證明技巧==
===雙射法===

{{main|雙射法}}

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

=== 算兩次 ===

{{main|算兩次}}

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

=== 抽屜原理 ===

{{main|抽屜原理}}

抽屜原理斷言，若<math>a</math>件物放入<math>b</math>個抽屜，而<math>a > b </math>，則必有某抽屜內放有多於一件物。此原理廣泛用於[[非構造性證明|存在性證明]]，即證明具某組合性質的物件存在，但不舉出例子。

=== 特異元素法 ===

{{main|{{le|特異元素法|Method of distinguished element}}}}

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

== 母函數 ==

{{main|母函數}}

母函數是[[形式冪級數]]（類似於[[多項式]]，但可以有無窮多個項），其系數依次對應[[數列]]的各項。以母函數表示數列，開拓了證明恆等式和求數列通項公式的新方法。數列<math>(a_n)</math>的（一般）母函數<math>G</math>由下式定義：

:<math>G(x) = \sum_{n=0}^{\infty} a_n x^n.</math>

== 遞歸關係 ==

{{main|遞歸關係}}

遞歸關係是利用數列某項<math>a_n</math>之前的其他項<math>a_i ( 0 \le i \le n-1)</math>定義該項。若證得數列的某條遞歸式，則可以已足以推導出此前未知的結論，不過一般而言，能找出[[解析解|通項公式]]則更佳。

== 參考文獻 ==
* {{cite book |first=J.H. |last=van Lint |first2=R.M. |last2=Wilson |year=2001 |title=A Course in Combinatorics |url=https://archive.org/details/courseincombinat0002lint |edition=2nd |publisher=Cambridge University Press |isbn=0-521-00601-5}}

[[Category:组合数学|*]]
[[Category:数学原理]]