From 7757599c3a66778d77c336648d45875c9f4d1ea2 Mon Sep 17 00:00:00 2001
From: FFjet <Leoleepaytser@hotmail.com>
Date: Sun, 21 Jul 2019 21:14:36 +0800
Subject: [PATCH] Update combination.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

修了很多内容
---
 docs/math/combination.md | 100 ++++++++++++++++++++---------------------------
 1 file changed, 42 insertions(+), 58 deletions(-)

diff --git a/docs/math/combination.md b/docs/math/combination.md
index a7fd6edd..dea19f96 100644
--- a/docs/math/combination.md
+++ b/docs/math/combination.md
@@ -1,4 +1,4 @@
-排列组合是组合数学中的一种。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。
+排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。
 
 在高中初等数学中，排列组合多是利用列表、枚举等方法解题。
 
@@ -14,20 +14,16 @@
 
 完成一个工程需要分 $n$ 个步骤， $a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。
 
-### 两原理的区别
-
-一个与分类有关，一个与分步有关；加法原理是 **分类完成** ，乘法原理是 **分步完成** 。
-
-## 排列与组合基础篇
+## 排列与组合基础
 
 ### 排列数
 
-从 $n$ 个不同元素中，任取 $m$ （ $m\leqslant n$ ， $m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$ ( $m\leqslant n$ ) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $A_n^m$ （或者是 $P_n^m$ ）表示。
+从 $n$ 个不同元素中，任取 $m$ （ $m\leq n$ ， $m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$ ( $m\leq n$ ) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$ （或者是 $\mathrm P_n^m$ ）表示。
 
 排列的计算公式如下：
 
 $$
-A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
+\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
 $$
 
  $n!$ 代表 $n$ 的阶乘，即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$ 。
@@ -35,49 +31,51 @@ $$
 公式可以这样理解： $n$ 个人选 $m$ 个来排队 ( $m \le n$ )。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推，第 $m$ 个（最后一个）可以选 $n-m+1$ 个，得：
 
 $$
-A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
+\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
 $$
 
 全排列： $n$ 个人全部来排队，队长为 $n$ 。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得：
 
 $$
-A_n^n = n(n-1)(n-2) \cdots 3 × 2 × 1 = n!
+\mathrm A_n^n = n(n-1)(n-2) \cdots 3 × 2 × 1 = n!
 $$
 
 全排列是排列数的一个特殊情况。
 
 ### 组合数
 
-从 $n$ 个不同元素中，任取 $m$ ( $m\leqslant n$ ) 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$ ( $m≤n$ ) 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $C_n^m$ （或者是 $\binom{m}{n}$ ）表示。
+从 $n$ 个不同元素中，任取 $m$ ( $m\leq n$ ) 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$ ( $m\leq n$ ) 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $\mathrm C_n^m$ 来表示。
 
 组合数计算公式
 
 $$
-C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n - m)!}
+\mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}
 $$
 
 如何理解上述公式？我们考虑 $n$ 个人 $m$ ( $m \le n$ ) 个出来，不排队，不在乎顺序 $C_n^m$ 。如果在乎排列那么就是 $A_n^m$ ，如果不在乎那么就要除掉重复，那么重复了多少？同样选出的来的 $m$ 个人，他们还要“全排”得 $A_n^m$ ，所以得：
 
 $$
-C_n^m \times m! = A_n^m\\
-C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}
+\mathrm C_n^m \times m! = \mathrm A_n^m\\
+\mathrm C_n^m = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!}
 $$
 
-组合数也常用 $\binom{n}{m}$ 表示，即 $C_n^m=\binom{n}{m}$ （注意他们是上下颠倒的）这个符号其实称作二项式系数的符号，与下文二项式定理有关。
+组合数也常用 $\displaystyle \binom{n}{m}$ 表示，读作「 $n$ 选 $m$ 」，即 $\displaystyle \mathrm C_n^m=\binom{n}{m}$ 。实际上，后者表意清晰明了，美观简洁，因此现在数学界普遍采用 $\displaystyle \binom{n}{m}$ 的记发而非 $\mathrm C_n^m$。
+
+组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。
 
-另外，我们认为当 $m>n$ 时， $A_n^m=C_n^m=0$ 。
+特别地，规定当 $m>n$ 时， $\mathrm A_n^m=\mathrm C_n^m=0$ 。
 
 ## 二项式定理
 
 在进入排列组合进阶篇之前，我们先介绍一个与组合数密切相关的定理——二项式定理。
 
-二项式定理就是一个展开式：
+二项式定理阐明了一个展开式的系数：
 
 $$
 (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i
 $$
 
-证明？数学归纳法。本质就是利用了 $\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ 做归纳。
+证明可以采用数学归纳法，利用 $\displaystyle \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ 做归纳。
 
 ## 排列与组合进阶篇
 
@@ -87,7 +85,7 @@ $$
 
 请大家一定要区分 **多重组合数** 与 **多重集的组合数** ！两者是完全不同的概念！
 
-多重集是指包含重复元素的广义集合。设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集，S 的全排列个数为
+多重集是指包含重复元素的广义集合。设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集，$S$ 的全排列个数为
 
 $$
 \frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}
@@ -99,11 +97,11 @@ $$
 \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}
 $$
 
-另外补一句， $\binom{n}{m}$ 其实等价于 $\binom{n}{m,n-m}$ ，只不过后者没人这么写。
+可以看出， $\displaystyle \binom{n}{m}$ 等价于 $\displaystyle \binom{n}{m,n-m}$ ，只不过后者较为繁琐，因而不采用。
 
 ### 多重集的组合数 1
 
-设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r(r<n_i,\forall i\in[1,k])$ ，从 S 中选择 r 个元素组成一个多重集的方案数就是 **多重集的组合数** 。这个问题等价于 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为
+设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r(r<n_i,\forall i\in[1,k])$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数就是 **多重集的组合数** 。这个问题等价于 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为
 
 $$
 \binom{r+k-1}{k-1}
@@ -111,7 +109,7 @@ $$
 
 ### 多重集的组合数 2
 
-上述其实是一个超级弱化版的多重集组合数，r 的范围太过局限。我们考虑这个问题：设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集。那么对于正整数 $r$ ，从 S 中选择 r 个元素组成一个多重集的方案数。
+考虑这个问题：设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集。那么对于正整数 $r$ ，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数。
 
 这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：
 
@@ -122,19 +120,19 @@ $$
 
 于是很自然地想到了容斥原理。容斥的模型如下：
 
-1.  全集： $\sum_{i=1}^kx_i=r$ 的非负整数解。
+1.  全集： $\displaystyle \sum_{i=1}^kx_i=r$ 的非负整数解。
 2.  属性： $x_i\le n_i$ 。
 
-于是设满足属性 i 的集合是 $S_i$ ， $\overline{S_i}$ 表示不满足属性 i 的集合，即满足 $x_i\ge n_i+1$ 的集合。那么答案即为
+于是设满足属性 $i$ 的集合是 $S_i$ ， $\overline{S_i}$ 表示不满足属性 $i$ 的集合，即满足 $x_i\ge n_i+1$ 的集合。那么答案即为
 
 $$
 \left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|
 $$
 
-推容斥的式子
+根据容斥原理，有：
 
 $$
-\begin{array}{l}
+\begin{split}
 \left|\bigcup_{i=1}^k\overline{S_i}\right|
 &=&\sum_i\left|\overline{S_i}\right|
 -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right|
@@ -145,10 +143,10 @@ $$
 -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1}
 -\cdots\\
 &&+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1}
-\end{array}
+\end{split}
 $$
 
-于是拿全集 $|U|=\binom{k+r-1}{k-1}$ 减去上式，得到多重集的组合数
+拿全集 $\displaystyle |U|=\binom{k+r-1}{k-1}$ 减去上式，得到多重集的组合数
 
 $$
 Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1}
@@ -158,59 +156,45 @@ $$
 
 ### 不相邻的排列
 
- $1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数不相邻数的组合有 $C_{n-k+1}^{k}$ 种。
-证明和上面的相同（其实就是懒得写），请自行证明 XD
-
-### 错位排列（错排）
-
-先看一个小问题： $5$ 本书，编号分别是 $1,2,3,4,5$ ，现在要把这 5 本书是放在编号 $1,2,3,4,5$ 的书架上，要求书的编号和书架的编号不一样，请问有多少种不一样的放置方法？
-
-再看一个小问题：编号为 $1,2,\cdots,n$ 的 $n$ 个球员分别住在编号为 $1,2,\cdots,n$ 的 $n$ 个房间里面。现规定每个人住一个房间，自己的编号不能和房间的编号一样。
+ $1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数不相邻数的组合有 $\displaystyle \binom {n-k+1}{k}$ 种。
 
-这就是错排问题。当 $n=3$ 时，只能为 312 或 231 这两种。
+### 错位排列
 
-那么错排问题的解题思路是什么呢？我们以第二个问题为例： **递推还是王道！** 
+错位排列，即「装错信封问题」，如下所述：
 
-刚开始所有球员都住在和自己编号一样的房间里面。然后错排开始了，第 $n$ 个球员从第 $n$ 个房间出来。
+一个人写了$n$封不同的信及相应的$n$个不同的信封，他把这$n$封信都装错了信封，问都装错信封的装法有多少种？
 
-第一种情况： $n$ 想和 $i(1 \le i \le n-1)$ 其中任何一个球员换房间，其他 $n-2$ 个人换房间的事情，他们就不管了。其他 $n-2$ 个球员的的错排数为 $d[n-2]$ ， $n$ 可以和前面 $1 \sim n-1$ 对换，所以有 $n-1$ 个 $d[n-2]$ 。
+我们分两种情况考虑:
 
-第二种情况： $n$ 想和 $i(1 \le i \le n-1)$ 其中任何一个球员换房间，但是 $n$ 只想 $i$ 住在第 $N$ 个房间，而 $n$ 不想住第 $I$ 个房间。
+- 前面$n-1$个信封全部装错；
+- 前面$n-1$个信封有一个没有装错其余全部装错。
 
-可能你会这样想：那么 $n$ 可以让 $j$ 住在第 $I$ 号房间里面，然后 $n$ 住在房间 $J$ 。抱歉， $j(1 \le j \le n-1,j\neq i)$ 生气 $n$ 为什么一开始就去找 $i$ 不直接来找 $j$ 。没办法， $n$ 把自己胸口的编码 $N$ 换成了 $I$ ，他假装自己是 $i$ ，然后错排 $1 \sim n-1$ （也就是 $d[n-2]$ ）的时候参与进去，这样自己就不会呆在第 $I$ 号房间了。所以有 $n-1$ 个 $d[n-1]$ 。
 
-如果理解了以上内容，那么错排的公式就出来了：
+对于第一种情况，前面$n-1$个信封全部装错：因为前面$n-1$个已经全部装错了，所以第n封只需要与前面任一一个位置交换即可，总共有$f(n-1)\times (n-1)$种情况。
 
-$$
-d_n = (n-1)(d_{n-2} + d_{n-1}) (n\geq 3)
-$$
-
-同时也有：
+对于第二种情况，前面$n-1$个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若$n-1$个信封中如果有一个没装错，那么我们把那个没装错的与$n$交换，即可得到一个全错位排列情况。
 
-$$
-d_n = n \times d_{n-1} + (-1)^n
-$$
+于是可得错位排列的递推式为$f(n)=(n-1)(f(n-1)+f(n-2))$。  
 
-错位排列数列为 $0,1,2,9,44,265,\cdots$ 
+错位排列数列的前几项为 $0,1,2,9,44,265$ 。
 
 ### 圆排列
 
- $n$ 个人全部来围成一圈为 $Q_n^n$ ，其中已经排好的一圈，从不同位置断开，又变成不同的队列。
-所以：
-
+ $n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$ 。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
+所以有
 $$
-Q_n^n \times n = A_n^n → Q_n = \frac{A_n^n}{n} = (n-1)!
+\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!
 $$
 
 由此可知部分圆排列的公式：
 
 $$
-Q_n^r = \frac{A_n^r}{r} = \frac{n!}{r \times (n-r)!}
+\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}
 $$
 
 ## 组合数性质 | 二项式推论
 
-由于组合数在 OI 中十分重要，因此我们讨论一下组合数的若干性质，这其中许多也是二项式的推论。
+由于组合数在 OI 中十分重要，因此在此介绍一些组合数的性质。
 
 $$
 \binom{n}{m}=\binom{n}{n-m}\tag{1}
-- 
2.11.0