# Chapter-7 Combination Mathematics # 第7章 組合數學 -------- 1. [FullPermutation 全排列](FullPermutation/) 2. [UniqueFullPermutation 唯一的全排列](UniqueFullPermutation/) 3. [Combination 組合](Combination/) 4. [DuplicableCombination （元素）可重復的組合](DuplicableCombination/) 5. [Subset 子集](Subset/) 6. [UniqueSubset 唯一的子集](UniqueSubset/) 7. [Permutation 排列](Permutation/) 8. [PermutationGroup 置換群](PermutationGroup/) 9. [Catalan 卡特蘭數](Catalan/) -------- #### 集合劃分 集合$$ X $$的劃分是$$ X $$的非空子集的集合，使得每一個$$ X $$的元素都只包含在這些子集的其中一個內。等價的說，集合$$ P $$是$$ X $$的劃分，如果： $$ (1) $$ $$ P $$的元素都是$$ X $$的子集，且不是空集； $$ (2) $$ $$ P $$的元素的并集等于$$ X $$； $$ (3) $$ $$ P $$的任意兩個元素的交集為空集； 集合$$ P $$中的元素也稱為$$ X $$的一個部分。例如$$ X = \{1,2,3,4,5,6\} $$的一個劃分是$$ P = \{ \{1 \},\{2,6\},\{3,4\},\{5\}\} $$，而$$ \{1\}, \{2,6\}, \{3,4\}, \{5\} $$都是$$ X $$的一個部分。 #### 加法原理 集合$$ X $$的元素數量等于$$ X $$的所有部分的元素數量之和，即$$ \mid X \mid = \mid X_1 \mid + \mid X_2 \mid + \dots + \mid X_n \mid $$。 #### 乘法原理 若集合$$ X $$中的所有元素都是由兩個數字組成的序列，即序偶$$ (a,b) $$。其中第一個元素$$ a $$來自擁有$$ p $$個元素的集合$$ A $$，第二個元素$$ b $$來自擁有$$ q $$個元素的集合$$ B $$。則集合$$ X $$的元素數量為$$ \mid X \mid = p \times q $$。 #### 減法原理 設集合$$ Y $$包含集合$$ X $$，集合$$ X $$在$$ Y $$中的補集為$$ X' $$，則$$ \mid X \mid = \mid Y \mid - \mid X' \mid $$。 #### 除法原理 集合$$ X $$被劃分為$$ p $$個部分，每個部分的元素數量都為$$ q $$，則$$ \mid X \mid = p \times q $$。 #### 階乘 $$ n! = \begin{cases} 1 & n = 0 \\ 1 \times 2 \times 3 \times \dots \times n & \forall n \gt 0 \end{cases} $$ 也可以寫作： $$ n! = \begin{cases} 1 & n = 0 \\ \prod_{k = 1}^n k & \forall n \gt 0 \end{cases} $$ 階乘的遞歸定義為： $$ n! = \begin{cases} 1 & n = 0 \\ (n-1)! \times n & \forall n \gt 0 \end{cases} $$ #### 組合 在擁有$$ n $$個不同元素（沒有兩兩相同的元素）的集合$$ A $$中，任意選出$$ m $$個元素（$$ m \leq n $$，$$ m $$和$$ n $$都是自然數，即正整數）組成另一個集合$$ B $$，稱$$ B $$為$$ A $$的一個子集。集合沒有順序的概念，對于集合$$ A $$中的任意元素（$$ \forall x \in A $$），都有$$ x \in B $$，同時集合$$ B $$中的任意元素（$$ \forall y \in B $$），都有$$ y \in A $$，則集合$$ A $$和$$ B $$是相同的。比如集合$$ s_1 = {1,2,3} $$、$$ s_2 = {3,2,1} $$是相同的兩個集合。 從$$ n $$個元素的集合中任意取出$$ m $$個元素能夠組成的不同集合的數量為： $$ C_m^n = \bigl( \begin{smallmatrix} n \\ m \end{smallmatrix} \bigr) = \frac{(P_m^n)}{m!} = \frac{n!}{m! \cdot (n-m)!} $$ 在二項式定理（https://en.wikipedia.org/wiki/Binomial_coefficient）中，二項式冪$$ (1+x)^n $$的多項式展開中$$ x^k $$（其中$$ k \in [0, n] $$）的系數即為$$ \bigl( \begin{smallmatrix} n \\ k \end{smallmatrix}\bigr) $$，等同于組合學中從$$ n $$個元素中選出$$ k $$個元素組成集合的所有組合數量。 例如對于$$ (x+1)^2 = 1x^0 + 2x^1 + x^2 $$，從$$ 2 $$個元素中選取$$ 1 $$個的組合數量為$$ 2 $$；選取$$ 2 $$個的組合數量為$$ 1 $$。 對于$$ (x+1)^3 = 1x^0 + 3x^1 + 3x^2 + x^3 $$，從$$ 3 $$個元素中選取$$ 1 $$個的組合數量為$$ 3 $$；選取$$ 2 $$個的組合數量為$$ 3 $$；選取$$ 3 $$個的組合數量為$$ 1 $$。 #### 排列 從$$ n $$個不同的元素（沒有兩兩相同的元素）中任意取$$ m $$個元素（$$ m \leq n $$，$$ m $$和$$ n $$都是自然數，即正整數）排成一列，得到排列$$ s $$。排列$$ s_1 = [1,2,3] $$、$$ s_2 = [3,2,1] $$、$$ s_3 = [2,3] $$兩兩各不相同，只有當兩個排列長度相同，且相同位置的元素也相同時，才稱這兩個排列相同。 從$$ n $$個元素中任意取出$$ m $$個元素組成的所有排列的數量為： $$ P_m^n = \frac{n!}{(n-m)!} $$ 也寫作：$$ A_m^n = \frac{n!}{(n-m)!} $$，維基百科中特別提到中國大陸教材中寫做$$ A_n^m $$。特別的當$$ m = n $$時，$$ P_m^n $$稱為全排列，$$ P_m^n = 1 \times 2 \times 3 \times \dots \times n = n! $$。 #### 數學符號表 * [https://en.wikipedia.org/wiki/List_of_mathematical_symbols](https://en.wikipedia.org/wiki/List_of_mathematical_symbols)