提高级-数学-组合数学：排列组合扩展（二项式定理、多重集合、等价类、多重集合的排列和组合，错排列、圆排列

# 二项式定理

二项式定理阐明了一个展开式的系数：

$$
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i
$$
其中，组合数 $\binom{n}{i} $ (也可写做$C_n^i$) 称为二项式系数。

利用二项式定理可以推导出一些常用公式，例如设 $x = 1, y = 1$，则有

$2^n = \sum\limits_{i = 0}^{n} \binom{n}{i} $
----

证明可以采用数学归纳法，利用 $\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}$ 做归纳。

----

二项式定理也可以很容易扩展为多项式的形式：

设 $n$ 为正整数，$x_i$ 为实数，

$$
(x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}
$$

其中的 $\dbinom{n}{n_1,n_2,\cdots,n_t}$ 是多项式系数，它的性质也很相似：

$$
\sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n
$$

---

# 多重集合
多重集是指包含重复元素的广义集合。

多重集合不满足集合的互异性，因此多重集合不是集合。
多重集合一般采用与集合类似的表示方法，例如： $\\{ 1, 2, 2, 3, 3, 3\\}$。
也可以表示成以下的形式

$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$ 组成的多重集，当$n_i=\infty$ 时表示有无限个 $a_i$。

一个元素在多重集合中出现的次数称为该元素在该多重集合中的重数。

---

# 多重集合上的排列
## 1. 
$S$ 的全排列个数为

$$
\frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}
$$

相当于把相同元素的排列数除掉了。具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$，且 $n=n_1+n_2+\ldots+n_k$。这 $n$ 个球的全排列数就是 **多重集的排列数**。多重集的排列数常被称作 **多重组合数**。

----

我们可以用多重组合数的符号表示上式：

$$
\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}
$$

可以看出，$\dbinom{n}{m}$ 等价于 $\dbinom{n}{m,n-m}$，只不过后者较为繁琐，因而不采用。

----
## 2.
多重集的每种元素都是无限个时，对于多重集的长度为 r 的 排列，其每个位置都有m种选择， 由乘法原理可知排列数为 $m^r$。

---
# 多重集上的组合

### 多重集的组合数 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$ 的非负整数解的数目，可以用插板法解决，答案为

$$
\binom{r+k-1}{k-1}
$$

----

### 多重集的组合数 2

考虑这个问题：设 $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$ 个元素组成一个多重集的方案数。

这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：

$$
\forall i\in [1,k],\ x_i\le n_i,\ \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$ 的集合（转化为上面插板法的问题三）。那么答案即为

$$
\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|
$$

----

根据容斥原理，有：

$$
\begin{aligned}
\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|
+\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right|
-\cdots\\
&+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\
=&\sum_i\binom{k+r-n_i-2}{k-1}
-\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{aligned}
$$

拿全集 $\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}
$$

其中 A 是充当枚举子集的作用，满足 $|A|=p,\ A_i<A_{i+1}$。

---

# 圆排列

$n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有

$$
\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!
$$

由此可知部分圆排列的公式：

$$
\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}
$$

---
# 错排列

### 定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 $1\sim n$ 的排列 $P$，如果满足 $P_i\neq i$，则称 $P$ 是 $n$ 的错位排列。

例如，三元错位排列有 $\{2,3,1\}$ 和 $\{3,1,2\}$。四元错位排列有 $\{2,1,4,3\}$、$\{2,3,4,1\}$、$\{2,4,1,3\}$、$\{3,1,4,2\}$、$\{3,4,1,2\}$、$\{3,4,2,1\}$、$\{4,1,2,3\}$、$\{4,3,1,2\}$ 和 $\{4,3,2,1\}$。错位排列是没有不动点的排列，即没有长度为 1 的循环。

----

### 容斥原理的计算

全集 $U$ 即为 $1\sim n$ 的排列，$|U|=n!$；属性就是 $P_i\neq i$. 套用补集的公式，问题变成求 $\left|\bigcup_{i=1}^n\overline{S_i}\right|$.

可以知道，$\overline{S_i}$ 的含义是满足 $P_i=i$ 的排列的数量。用容斥原理把问题式子展开，需要对若干个特定的集合的交集求大小，即：

$$
\left|\bigcap_{i=1}^{k}S_{a_i}\right|
$$

----

其中省略了 $a_i<a_{i+1}$ 的条件以方便表示。上述 $k$ 个集合的交集表示有 $k$ 个变量满足 $P_{a_i}=a_i$ 的排列数，而剩下 $n-k$ 个数的位置任意，因此排列数：

$$
\left|\bigcap_{i=1}^{k}S_{a_i}\right|=(n-k)!
$$

----

那么选择 $k$ 个元素的方案数为 $\dbinom{n}{k}$，因此有：

$$
\begin{aligned}
\left|\bigcup_{i=1}^n\overline{S_i}\right|
&=\sum_{k=1}^n(-1)^{k-1}\sum_{a_{1,\cdots,k} }\left|\bigcap_{i=1}^{k}S_{a_i}\right|\\\\
&=\sum_{k=1}^n(-1)^{k-1}\dbinom{n}{k}(n-k)!\\\\
&=\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\\\\
&=n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!}
\end{aligned}
$$

----

因此 $n$ 的错位排列数为：

$$
D_n=n!-n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!}=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
$$

错位排列数列的前几项为 $0,1,2,9,44,265$（[OEIS A000166](http://oeis.org/A000166)）。

----

### 递推的计算

把错位排列问题具体化，考虑这样一个问题：

$n$ 封不同的信，编号分别是 $1,2,3,4,5$，现在要把这五封信放在编号 $1,2,3,4,5$ 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设考虑到第 $n$ 个信封，初始时暂时把第 $n$ 封信放在第 $n$ 个信封中，然后考虑两种情况的递推：

-   前面 $n-1$ 个信封全部装错；
-   前面 $n-1$ 个信封有一个没有装错其余全部装错。

对于第一种情况，前面 $n-1$ 个信封全部装错：因为前面 $n-1$ 个已经全部装错了，所以第 $n$ 封只需要与前面任一一个位置交换即可，总共有 $D_{n-1}\times (n-1)$ 种情况。

----

对于第二种情况，前面 $n-1$ 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 $n-1$ 个信封中如果有一个没装错，那么把那个没装错的与 $n$ 交换，即可得到一个全错位排列情况。

其他情况，不可能通过一次操作来把它变成一个长度为 $n$ 的错排。

于是可得，错位排列数满足递推关系：

$$
D_n=(n-1)(D_{n-1}+D_{n-2})
$$

这里也给出另一个递推关系：

$$
D_n=nD_{n-1}+{(-1)}^n
$$

----

### 其他关系

错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数：

$$
D_n=\begin{cases}
    \left\lceil\frac{n!}{\mathrm{e}}\right\rceil, & \text{if }n\text{ is even}, \\\\
    \left\lfloor\frac{n!}{\mathrm{e}}\right\rfloor,            & \text{if }n\text{ is odd}.
\end{cases}
$$

随着元素数量的增加，形成错位排列的概率 P 接近：

$$
P=\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}}
$$

---

# 等价类