# 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)
- Content 目錄
- Preface 前言
- Chapter-1 Sort 第1章 排序
- InsertSort 插入排序
- BubbleSort 冒泡排序
- QuickSort 快速排序
- MergeSort 歸并排序
- Chapter-2 Search 第2章 搜索
- BinarySearch 二分查找法(折半查找法)
- BruteForce 暴力枚舉
- Recursion 遞歸
- BreadthFirstSearch 廣度優先搜索
- BidirectionalBreadthSearch 雙向廣度搜索
- AStarSearch A*搜索
- DancingLink 舞蹈鏈
- Chapter-3 DataStructure 第3章 數據結構
- DisjointSet 并查集
- PrefixTree(TrieTree) 前綴樹
- LeftistTree(LeftistHeap) 左偏樹(左偏堆)
- SegmentTree 線段樹
- FenwickTree(BinaryIndexedTree) 樹狀數組
- BinarySearchTree 二叉查找樹
- AVLTree AVL平衡樹
- RedBlackTree 紅黑樹
- Chapter-4 DynamicProgramming 第4章 動態規劃
- Chapter-5 GraphTheory 第5章 圖論
- Chapter-6 Calculation 第6章 計算
- LargeNumber 大數字
- Exponentiation 求冪運算
- Chapter-7 CombinatorialMathematics 第7章 組合數學
- FullPermutation 全排列
- UniqueFullPermutation 唯一的全排列
- Combination 組合
- DuplicableCombination (元素)可重復的組合
- Subset 子集
- UniqueSubset 唯一的子集
- Permutation 排列
- PermutationGroup 置換群
- Catalan 卡特蘭數
- Chapter-8 NumberTheory 第8章 數論
- Sieve 篩選算法
- Euclid 歐幾里得
- EuclidExtension 歐幾里得擴展
- ModularLinearEquation 模線性方程
- ChineseRemainerTheorem 中國剩余定理
- ModularExponentiation 模冪運算
- Chapter-9 LinearAlgebra 第9章 線性代數
- Chapter-10 AnalyticGeometry 第10章 解析幾何
- Chapter-11 TextMatch 第11章 文本匹配
- SimpleMatch 簡單匹配
- AhoCorasickAutomata AC自動機
- KnuthMorrisPratt KMP匹配算法
- RabinKarp RabinKarp算法
- BoyerMoore BoyerMoore算法
- Chapter-12 GameTheory 第12章 博弈論
- BashGame 巴什博弈
- WythoffGame 威佐夫博弈
- NimGame 尼姆博弈