组合数学（学习笔记）
2.1 四个基本计数原理
加法原理：
集合\(S\)被划分成两两不相交的部分\(S_1, S_2, S_3,\cdots,S_m\)，则
\[|S| = |S_1|+|S_2|+|S_3|+\cdots+|S_m| \]乘法原理：
集合\(S\)的元素是有序对\((a, b)\)，\(a\)来自大小为\(p\)的集合，\(b\)来自大小为\(q\)的集合，则
\[|S| = p \times q \]减法原理：
集合\(A，U\)且\(A\sub U\)。集合\(\overline{A}\)为\(A\)在\(U\)中的补集。
\[\left| A\right| =\left| U\right| -\left| \overline{A}\right| \]除法原理：
有限集合\(S\)，将其划分成\(k\)个大小相同9的部分。
\[k=\dfrac{\left| S\right| }{一个部分的对象数目} \]2.2 集合的排列
定理 2.2.1:
\(n,r\in N^*且r\leq n\)，有
\[P(n,r) = \dfrac{n!}{\left( n-r\right) !} = n\times(n-1)\times\cdots\times(n-r+1) \]定理 2.2.2：
因为\(1\)种循环排列对应\(r\)种线性排列。
\(n\)个元素的循环排列为
\[\dfrac{P\left( n,r\right) }{r}=\dfrac{n!}{r\cdot \left( n-r\right) !} \]2.3 集合的组合
定理 2.3.1：
对于\(0\le r\le n\)，有
\(P\left( n,r\right) =r!\begin{pmatrix} n \\ r \end{pmatrix}\)，其中\(r!\)决定\(r\)个数的顺序。
因此
\[\begin{pmatrix} n \\ r \end{pmatrix}=\dfrac{n!}{r!\left( n-r\right) !} \]推论 2.3.2：
对于\(0\le r\le n\)， 有
\[\begin{pmatrix}n \\r\end{pmatrix}=\begin{pmatrix}n \\n-r\end{pmatrix} \]推论 2.3.3 (帕斯卡定理):
对于所有满足\(1\leq k\leq n-1\)的整数\(n\)和\(k\)，有
\[\begin{pmatrix}n \\k\end{pmatrix}=\begin{pmatrix}n-1 \\k\end{pmatrix}+\begin{pmatrix}n-1 \\k-1\end{pmatrix} \]定理 2.3.4：
对于\(n\ge0\)，有
\[\begin{pmatrix}n \\0\end{pmatrix}+\begin{pmatrix}n \\1\end{pmatrix}+\begin{pmatrix}n \\2\end{pmatrix}+\ldots +\begin{pmatrix}n \\n\end{pmatrix}=2^{n} \]这等于\(n\)元素集合的子集数量。
2.4 多重集合的排列
设\(S\)是有\(k\)种不同类型对象的多重集合，每一元素都有无限重复数。
那么，\(S\)的\(r\)排列的数目是\(k^r\)。
标签：begin,right,end,组合,pmatrix,集合,数学,left From： https://www.cnblogs.com/Peng1984729/p/18220001