组合数学
cqbzlwz
·
2022-07-30 11:12:25
·
个人记录
一、前言
本文是对于学习组合数学的笔记，整理了部分知识点和习题。
比赛链接：组合数学 & 盒子与球
二、知识点&习题
1.排列组合
1.0 前置
排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。（摘自 \texttt{oi-wiki} ）
简单地说，排列数和组合数的区别在于，排列数考虑顺序 ，组合数不考虑顺序 。
1.1 加法&乘法原理
在了解组合数和排列数之前，先来考虑两个非常重要的原理：
1.加法原理：完成一件事共有 n 种不同的选择 ，其中第 i 种选择有 a_i 种可能的情况，那么一共有 \sum\limits_{i=1}^{n}a_i 种情况。
2.乘法原理：完成一件事共有 n 个步骤 ，第 i 步有 a_i 种选择，那么总共选择的方案数有 \prod\limits_{i=1}^{n}a_i 种。
1.2 排列数&组合数
1.2.1 排列数
从 n 个不同元素中，任取 m （m\leq n ，m 与 n 均为自然数，下同）个元素按照一定的顺序 排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列；从 n 个不同元素中取出 m 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 A_n^m 表示。
如何计算呢？
可以这样理解：n 个人选 m 个排成一排。第一个位置可以选 n 个，第二个位置可以选 n-1 个，以此类推，第 m 个可以选 n-m+1 个，即：
\color{red}{\boxed{A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}}}
全排列：n 个人全部来排队，m=n ，此时 A_n^n=\frac{n!}{0!}=n! 。
全排列是排列数的一个特殊情况。
1.2.2 组合数
从 n 个不同元素中，任取 m 个元素组成一个集合 （即不考虑顺序），叫做从 n 个不同元素中取出 m 个元素的一个组合；从 n 个不同元素中取出 m 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数。用符号 C_n^m 来表示。另外还有一种常用的表示方法 \begin{pmatrix}n\\m\end{pmatrix} ，由于好写、好看，更加常用，但是要注意上面是 n （选的元素个数），下面是 m 。
组合数计算公式：可以类推排列数的公式，只需去除顺序。而对于 m 个人的顺序，显然有 A_m^m=m! 种。因此我们只要除以 m! 即可。得出公式：
\color{red}{\boxed{C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}}}
另外，C_n^m=\frac{m}{n-m+1}C_n^{m-1} 在 n 固定时也是较快的求组合数方式，可以用上面的公式自行证明。
组合数具有一个性质：\begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n\\n-m\end{pmatrix} ，可以想成是在 n 个物品中选出 n-m 个不要，这与在 n 个物品中选出 m 要是一样的。需要注意，组合数没有这个性质 。
1.2.3 盒子与球
有时我们会遇到这样的问题：把若干物品分成若干份，求总方案数。显然与排列组合有关。这类问题通常可以转化为：将 n 个小球放进 m 个盒子中，求方案数。而这些问题又以小球是否能视为相同、盒子能否视为相同、盒子能否为空。前两者显然是对于考不考虑顺序，而后者则是决定方案是否成立的重要条件。因此共有 2^3=8 种问题。
为了避免篇幅过长，且网上有许多资料，以及可以自己进行推导，不再进行赘述。推荐阅读：当小球遇上盒子
1.2.4 杨辉三角
杨辉三角，是由杨辉发现的三角，国外也叫帕斯卡三角。杨辉三角已经是大众耳熟能详的东西了，给出这个三角的一部分（略丑，勿喷）：
\begin{pmatrix}1\\1&1\\1&2&1\\1&3&3&1\\1&4&6&4&1\\1&5&10&10&5&1\\1&\dots&\dots&\dots&\dots&\dots&1\end{pmatrix}
杨辉三角的递推式为：a_{i,j}=a_{i-1,j}+a_{i-1,j-1}
而且，杨辉三角第 n 行、第 m 列的元素，就等于 \begin{pmatrix}n-1\\m-1\end{pmatrix}
，因此，组合数能以杨辉三角的递推式计算：\color{red}{\boxed{\begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n-1\\m\end{pmatrix}+\begin{pmatrix}n-1\\m-1\end{pmatrix}}} 。
也可以进行算数证明：
\ \ \ \ \ C_{n-1}^m+C_{n-1}^{m-1}
=\dfrac{(n-1)!}{m!(n-m-1)!}+\dfrac{(n-1)!}{(m-1)!(n-m)!}
=\dfrac{\dfrac{(n-1)!(n-m)}{m}}{(m-1)!(n-m)!}+\dfrac{(n-1)!}{(m-1)!(n-m)!}
=\dfrac{\dfrac{(n-1)!(n-m)+(n-1)!m}{m}}{(m-1)!(n-m)!}
=\dfrac{(n-1)!(n-m)+(n-1)!m}{m!(n-m)!}
=\dfrac{(n-1)!(n-m+m)}{m!(n-m)!}
=\dfrac{n!}{m!(n-m)!}
=C_n^m
还能这样思考：考虑第 n 个物品选或不选，若选，有 C_{n-1}^{m-1} 种方案（即前 n-1 个物品中选 m-1 个，因为 n 占用了一个位置），若不选，有 C_{n-1}^m 种方案（即前 n-1 个物品中选 m 个），合起来根据组合数的定义可以证明。
1.2.5 二项式定理
二项式定理与组合数密切相关，可以互相转化，在题目中也常常出现。先给出式子：
\color{red}{\boxed{(a+b)^n=\sum\limits_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}a^ib^{n-i}}}
二项式系数就是组合数，下面给出二项式定理的证明：
显然，(a+b)^n=\begin{matrix}\underbrace{(a+b)(a+b)\cdots(a+b)}\\n\texttt{个}\end{matrix}
可以看成是在作乘法分配律时，有 n 个 a 或 b 可选，每一次可以选 a 或 b ，选 n 次。因此一个展开后的项，由于没有常数项可选，只能选 k(0\leq k\leq n) 个 a 和 n-k 个 b 。要求 a^kb^{n-k} 的系数，就是求在 n 个括号中选 k 个 a 的方案数，即 C_n^k ，证毕。
另外，可以用数学归纳法证明。
首先，n=1 时，显然有 (a+b)^n=a+b=C_1^0a^0b^1+C_1^1a^1b^0=1\cdot b+1\cdot a 。
其次，假设 m=n-1 ，且 (a+b)^m=\sum\limits_{i=0}^{m}\begin{pmatrix}m\\i\end{pmatrix}a^ib^{m-i} 成立。
则 (a+b)^n
=(a+b)^m\cdot(a+b)
=b\sum\limits_{i=0}^{m}\begin{pmatrix}m\\i\end{pmatrix}a^ib^{m-i}+a\sum\limits_{i=0}^{m}\begin{pmatrix}m\\i\end{pmatrix}a^ib^{m-i}
=\sum\limits_{i=0}^{m}\begin{pmatrix}m\\i\end{pmatrix}a^{i}b^{m-i+1}+\sum\limits_{i=0}^{m}\begin{pmatrix}m\\i\end{pmatrix}a^{i+1}b^{m-i}
=b^{m+1}+\sum\limits_{i=1}^m\begin{pmatrix}m\\i\end{pmatrix}a^ib^{m-i+1}+\sum\limits_{i=1}^{m+1}\begin{pmatrix}m\\i-1\end{pmatrix}a^{i}b^{m-i+1}
=a^{m+1}+b^{m+1}+\sum\limits_{i=1}^m\begin{pmatrix}m\\i\end{pmatrix}a^ib^{m-i+1}+\sum\limits_{i=1}^{m}\begin{pmatrix}m\\i-1\end{pmatrix}a^{i}b^{m-i+1}
=\begin{pmatrix}n\\0\end{pmatrix}a^n+\begin{pmatrix}n\\n\end{pmatrix}b^n+\sum\limits_{i=1}^m\left[\begin{pmatrix}m\\i\end{pmatrix}+\begin{pmatrix}m\\i-1\end{pmatrix}\right]a^ib^{m-i+1}
由 \begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n-1\\m\end{pmatrix}+\begin{pmatrix}n-1\\m-1\end{pmatrix} 得：
$=\begin{pmatrix}n\\0\end{pmatrix}a^n+\begin{pmatrix}n\\n\end{pmatrix}b^n+\sum\limits_{i=1}^m\begin{pmatrix}n\\i\end{pmatrix}a^ib^{m-i+1}
=\sum\limits_{i=0}^{n}\begin{pmatrix}n\\i\end{pmatrix}a^ib^{n-i}
即原式成立。
习题：计算系数
模板题。
1.3 排列问题
1.3.1 错排问题
考虑这样一个问题：
首先要知道，对于任意 $n$ 封信，其错排数量一定固定，因此可以考虑递推。
假设我们考虑到第 $i$ 个信封，初始时我们暂时把第 $i$ 封信放在第 $i$ 个信封中，然后考虑两种情况的递推：
- 前面 $i-1$ 个信封全部装错；
- 前面 $i-1$ 个信封有一个没有装错其余全部装错。
对于第一种情况，前面 $i-1$ 个信封全部装错：因为前面 $i-1$ 个已经全部装错了，所以第 $i-1$ 封只需要与前面任一一个位置交换即可，总共有 $(i-1)f_{i-1}$ 种情况。
对于第二种情况，前面 $i-1$ 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 $i-1$ 个信封中如果有一个没装错，那么我们把那个没装错的与 $i$ 交换，即可得到一个错位排列情况，而剩下的 $i-2$ 个能构成一个错排，共有 $(i-1)f_{i-2}$ 种情况。
其他情况，我们不可能通过一次操作来把它变成一个长度为 $i$ 的错排。
于是可得错位排列的递推式为 $f_i=(i-1)(f_{i-1}+f_{i-2})$。
习题：[放旗子](http://222.180.160.110:1024/problem/3933)
题目的障碍是一个迷惑项，由于任意两个障碍不在同一行与同一列，因此这是一个典型的错排问题。因为我们可以将任意两行的障碍交换，使得第 $i$ 行的障碍在第 $i$ 列，相当于交换两行的棋子，不影响答案。
#### 1.3.2 圆排列
不太常用的排列...
首先考虑将 $n$ 个人中选 $m$ 个拿来排队，如果排成一行，有 $A_n^m$ 种方案。
此时要消去重复的情况，因为对于一个圆排列，如果将其进行旋转，与它相同的排列是一种排列。很显然，这种排列有 $m$ 种。
因此，若记 $Q_n^m$ 表示 $n$ 个人中选 $m$ 个人，排成一个圆的方案总数，则 $Q_n^m=\dfrac{A_n^m}{m}=\dfrac{n!}{m(n-m)!}$，要与组合数区分开。
#### 1.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$ 组成的多重集，$S$ 的全排列个数为：
$$\color{red}{\boxed{\frac{n!}{\prod\limits_{i=1}^{k}n_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}}}$$
相当于把相同元素的排列数除掉了。具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$，且 $n=\sum\limits_{i=1}^{k}n_i$。这 $n$ 个球的全排列数就是多重集 $S$ 的排列数。多重集的排列数常被称作多重组合数。我们可以用多重组合数的符号表示上式：
$$\color{red}{\boxed{\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod\limits_{i=1}^{k}n_i!}}}$$
一定要注意，**多重组合数** 与 **多重集的组合数**是不同的概念！
习题：[Ant Counting 数蚂蚁](http://222.180.160.110:1024/problem/16023)
怎么说呢。。。还是比较简单的吧，反正我是打了个计数 DP。~~（对我只会这个）~~
然后是组合数，有两种情况：
1. 设一个多重集 $S$，变量的定义与上面相同。设一个正整数 $m(m\leq n_i,\forall i\in[1,k])$，则从 $n$ 个元素中选出 $m$ 个元素构成一个集合的方案总数，就是多重集的组合数。相当于从 $n_i$ 个元素中选 $x_i$ 个，使得 $\sum\limits_{i=1}^{k}x_i=m$。可以用插板法解决，因此多重集的组合数为：$\binom{m+k-1}{k-1}$。
2. 其他条件和1.相同，但是 $m\leq n$，如何解决？由于插板法可能会使分配的 $x_i > n_i$，因此不能**直接**用插板法，可以考虑容斥原理。请读者阅读了下面的内容后再回来自行思考。懒得打 $\LaTeX$，直接 [link](https://oiwiki.org/math/combinatorics/combination/#2) 吧。
习题：自己找吧（~~好吧是我没做过，但好像老师也没有在[这里](http://222.180.160.110:1024/contest/2673)放多重集组合数？貌似[L.条形码](http://222.180.160.110:1024/problem/8989)能作为习题，但我打的 `dp` 不太像？~~）
附[条形码](http://222.180.160.110:1024/problem/8989)代码，有大佬能看一下这到底是不是多重集组合数吗？
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, m, s, dp[40][40];
char a[40];
signed main() {
scanf("%d%d%d", &n, &k, &m);
dp[0][0] = 1;
for (int i = 1; i <= k; ++i) {
for (int j = 1; j <= n; ++j) {
for (int l = 1; l <= min(m, j); ++l) {
dp[i][j] += dp[i - 1][j - l];
}
}
}
printf("%lld\n", dp[k][n]);
scanf("%d", &s);
for (int c = 1; c <= s; ++c) {
scanf("\n%s", a + 1);
int len = strlen(a + 1), cnt = 0, p[40];
for (int i = 1; i <= len; ++i) {
if (a[i] != a[i - 1]) p[++cnt] = 1;
else ++p[cnt];
}
int tmp = 0, ans = 0;
for (int i = 1; i <= k; ++i) {
const int o1 = min(p[i], n - tmp), o2 = min(n - tmp, m);
if (i & 1) for (int j = 1; j < o1; ++j) ans += dp[k - i][n - tmp - j];
else for (int j = p[i] + 1; j <= o2; ++j) ans += dp[k - i][n - tmp - j];
tmp += p[i];
}
printf("%lld\n", ans);
}
return 0;
}
```
## 2.卡特兰数
### 2.1 卡特兰数
#### 2.1.1 基本公式
[加深理解](https://oiwiki.org/math/combinatorics/catalan/)
先看一道模板题：[编程社买书](http://222.180.160.110:1024/problem/359)
可以考虑 `dp`，很容易想到定义状态 $dp_{i,j}$ 表示前 $i+j$ 个同学中有 $i$ 个带 $100$ 元的，$j$ 个带 $50$ 元的方案总数。状态转移也很显然：$dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}[i\leq j]$，初始化是 $dp_{0,i}=1(1\leq i\leq n)$，答案即为 $dp_{n,n}$。但是要开高精度。。。
其实这已经是一种卡特兰数的 $O(n^2)$ 做法了。这事实上就是卡特兰数，也有一种定义一维状态的 $O(n^2)$ 做法，从[这个](http://222.180.160.110:1024/problem/350)的角度更好理解，~~我不信有人没做过~~。
至于其它的式子，码到这也是很累了，就不放了，~~`wiki` 已经讲得很清楚了~~，要根据实际情况灵活选择。
#### 2.1.2 应用方面：
求 $(0,0)$ 到 $(n,m)$ 有一堆限制的方案总数，通常都可以对原式进行变形：[网格](http://222.180.160.110:1024/problem/244)
以 $n=m$ 时类似的方法推式子，直接放代码吧。
```cpp
for (int i = 1; i <= (n + m) / 2; ++i) dp[i] = dp[i - 1] * (n + m - i + 1) / i;
cout << dp[min(n, m)] - dp[min(n + 1, m - 1)];
```
## 3.容斥原理
### 3.1 容斥原理
#### 3.1.1 入门
~~（默认小学课内就学过就放个标题吧）~~
#### 3.1.2 容斥原理
设集合 $V$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，$S_i$ 中有 $a_i$ 个元素，那么
$$\left|\bigcup\limits_{i=1}^{n}S_i\right|=\sum\limits_{j=1}^{n}(-1)^{m-1}\sum\limits_{a_i<a_{i+1}}\left|\bigcap\limits_{i=1}^{j}S_{a_i}\right|$$
还是很好理解的，$a_i<a_{i+1}$ 是为了避免有重复的选择。记住一个口诀：**奇加偶减**。即，如果当前选的属性有奇数种，当前的元素个数就是加，否则是减。
很多题目都要用容斥的思想去求方案数，也要根据实际情况调整公式，公式不能死记硬背。
## 4.鸽巢原理
### 4.1 鸽巢原理（抽屉原理）
#### 4.1.1 鸽巢原理1
将 $n$ 个物体，划分为 $n-1$ 组，那么有至少一组有两个（或以上）的物体。
证明方法采用反证法：假如每一组有至多 $1$ 个物体，那么总共最多有 $n-1$ 个物体，而实际上有 $n$ 个物体，矛盾。
#### 4.1.2 鸽巢原理2
将 $n$ 个物体分为 $m$ 组，那么至少存在一组，含有大于或等于 $\left\lceil\dfrac{n}{m}\right\rceil$ 个物品。
也可以采用反证法证明：若每一组含有小于 $\left\lceil\dfrac{n}{m}\right\rceil$ 个物体，则其一共最多有 $m\left(\left\lceil\dfrac{n}{m}\right\rceil-1\right)$ 个，小于 $m\cdot \dfrac{n}{m}=n$ 个，矛盾。
#### 4.1.3 应用
常被用于证明存在性证明和求最坏情况下的解。
习题：[Halloween treats](http://222.180.160.110:1024/problem/30152)
移步至 [题解](https://www.luogu.com.cn/blog/luowenzuo/solution-uva11237)
## 5.康托展开
### 5.1 康托展开基础
#### 5.1.1 康托展开
康托展开能在 $O(n^2)$ 的时间复杂度内求出一个 $1\sim n$ 的排列的字典序排名。
#### 5.1.2 实现
对于排列 $[2,5,3,4,1]$，第一位为 $1$ 的排列肯定在它前面，而这样的排列有 $4!$ 种。接下来考虑第二位。由于在前面统计了第一位为 $1$ 的情况，因此第二位比它小的 $1,2,3,4$ 能作出贡献，就是 $4\times 3!$ 种。
然而，这真的正确吗？注意到此时第一位已经选了 $2$，因此第二位只能选 $1,3,4$。
所以对于第 $i(2\leq i\leq n)$ 位，它能对排名做出贡献的是**前面没有出现过且比它小的数字数量** $\times (n-i)!$。
对于刚刚的那个例子，它的排名就是 $1\times4!+3\times3!+1\times 2!+1\times1!+1=46$，由于排名是从 $1$ 开始计数，所以最后要加 $1$。
#### 5.1.3 树状数组
我们在计算答案时用到了**前面没有出现过且比它小的数字数量**，这个东西的值可以用权值树状数组（当然可以用线段树）维护，使时间复杂度降至 $O(n\log n)$。
#### 5.1.4 逆康托展开
因为排列的排名和排列是一一对应的，所以可以通过类似上面的过程倒推回来。
还是以上面的排名举例子，因为 $46$ 是排名所以先减一。
由于 $4!$ 大于 $3\times 3!+2\times 2!+1\times 1$，所以第一位 $\times 4!$ 小于 $45$ 且 $45$ 减去这个值后一定小于这个值，从而知道第一位是 $\left\lfloor\dfrac{45}{4!}\right\rfloor+1=2$（自行思考为什么要加 $1$）。
接下来，用 $45$ 减去 $1\times 4!$，得 $21$,这就是刚刚我们算的 $3\times3!+1\times2!+1\times1!$，相似之处还是有的。第二位有 $\left\lfloor\dfrac{21}{3!}\right\rfloor=3$ 个数小于它且没出现过，因此第二位就是 $5$（因为 $1$ 已经出现过，所以不是 $4$）。
时间复杂度 $O(n^2)$。
#### 5.1.5 逆康托展开的优化
对于逆康托展开，也可以用树状数组把时间复杂度降至 $O(n\log n)$。
## 三、后记
这个暑假学的组合数学就整理成这样吧。从 7.31 第一次发出来到今天 9.6 完善，时隔大概一个月，又整改了一下。现在去写搁置了一个月的数论了。。。