OI数学总结-组合数学

施工中，咕咕咕….

排列组合

更多详见 小蓝书 16.1

下面两个指的是无重复的排列与组合

排列数

从 $n$ 个不同元素中取 $k(k\le n)$ 个不同元素，并按一定顺序排成一列的方案数

$$\mathrm{A}_{n}^{k} = \frac{n!}{(n-k)!}$$

也可写作 $\mathrm{P}_{n}^{k}$ 或直接用组合数写法 $k! \times \binom{n}{k}$

代码求解

$O(n)$ 计算

例如求解 $A_{n-m+1}^{m} \bmod p$

int res=1;
for(int i=n-m+1; i>=n-2*m+2; i--)
    res=res*i%p;
cout << res << '\n'

组合数

从 $n$ 个不同元素中取 $k(k \le n)$ 个不同元素的方案数

$$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$$

高中一般记作 $\mathrm{C}_n^{k}$ ，不是很推荐使用。

特别地，规定当 $k > n$ 时， $\mathrm{A}_n^{k} = \mathrm{C}_n^{k}=0$

代码求解

$O(n^2)$ 递推

for(int i=0; i<=1000; i++)
{
    C[i][0]=1;
    for(int j=1; j<=i; j++)
        C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}

$O(p)$ Lucas定理

详见 [OI数学总结-数论]

P3807 【模板】卢卡斯定理/Lucas 定理

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)
int Q,n,m,p;
int fac[N];
int qpow(int a,int b,int p)
{
	int ans=1,base=a;
	while(b)
	{
		if(b&1)ans=ans*base%p;
		base=base*base%p;
		b>>=1;
	}
	return ans;
}
// n 选 m
int C(int n,int m,int p)
{
	if(n<m)return 0;
	return fac[n]*qpow(fac[m],p-2,p)%p*qpow(fac[n-m],p-2,p)%p;
}
int lucas(int n,int m,int p)
{
	if(!m)return 1;
	return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
signed main()
{
	cin >> Q;
	while(Q--)
	{
		cin >> n >> m >> p;
		fac[1]=fac[0]=1;
		for(int i=2; i<=n+m; i++)
			fac[i]=fac[i-1]*i%p;
		cout << lucas(n+m,m,p) << '\n'; // C(n+m,n)
	}
	return 0;
}

排列组合常用公式

$$\sum\limits_{i=0}^n \dbinom{n}{i}^2 = \dbinom{2n}{n} \tag{1}$$

这个可以单独拉出来讲，到时候写一个。

$$\sum_{i=0}^n\dbinom{i}{m} = \dbinom{n+1}{m+1}\tag{2}$$

$(2)$ 可以通过杨辉三角（数学归纳法）简单证明。

$$\sum_{i=l}^r\left(\begin{array}{l} i \\ k \end{array}\right)=\left(\begin{array}{l} r+1 \\ k+1 \end{array}\right)-\left(\begin{array}{c} l \\ k+1 \end{array}\right)$$

证明的话直接移项，然后一直根据递推式合并即可。

---

容斥原理

容斥原理(principle of inclusion-exclusion)：令 $X$ 为一个有限集合，$P_1, P_2,\dots , P_m$ 是一些性质的集合，对于任意 $S \subseteq [m]$ ，即 $S\subseteq \{1,2,\cdots,m\}$ ，定义 $N(S) = \{x \in X \mid \forall i \in S : x \text{ has } P_i\}$ 。那么 $X$ 中满足性质 $P_{1\sim m}$ 的元素个数为

$$\sum_{S \subseteq [m]} (-1)^{|S|+1} \left|N(S)\right|$$

如果是不满足任何一个性质的话，把指数中的 $|S|+1$ 改成 $|S|$ 即可。

特别地，对于任意的 $S \subseteq [m]$ ，如果 $N(S)$ 只和 $S$ 的大小（即 $|S|$ ）有关，那么式子可以化简为

$$\sum_{i=0}^{m} (-1)^{i+1} \binom{m}{i} N(i)$$

其中 $N(i)$ 表示对于任意满足 $S \subseteq [m],|S|=i$ 的 $N(S)$ 值。

如果是不满足任何一个性质的话，把指数中的 $i+1$ 改成 $i$ 即可。

容斥原理的常用技巧：

1. 定义一些“坏性质” $P_1,\dots,P_m$

2. 找到对于每个 $S\subseteq [m]$ 计算 $N(S)$ 的方法

3. 套用容斥原理计算不满足任何一个“坏性质”的元素个数

4. 注意这里求的是不满足任何坏性质，因此用以下公式

   $$\sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right|$$

---

鸽巢原理（抽屉原理）

假如有 $n+1$个元素放到 $n$ 个集合中去，其中必定有一个集合里至少有两个元素。

应用

1. 任意 $n+1$ 个数中至少有 $2$ 个数与 $n$ 同余

---

第二类斯特林数

第二类斯特林数记作 $S(n,k)$ 或 $\left\{\begin{array}{l}n \\k\end{array}\right\}$ 。

表示将 $n$ 个两两不同的元素划分为 $k$ 个无区别的非空子集的方案数。

换个说法，$n$ 个不同的球放到 $m$ 个相同的盒子，不可以有空盒子的方案数。

注意，如果是 $n$ 个相同的球，那就是插板法的问题了，所以不同的球是第二类斯特林数的关键。

边界：

$$\left\{\begin{array}{l}n \\0\end{array}\right\} = [n=0]$$

递推式：

$$\left\{\begin{array}{l} n \\ k \end{array}\right\}=\left\{\begin{array}{l} n-1 \\ k-1 \end{array}\right\}+k\left\{\begin{array}{c} n-1 \\ k \end{array}\right\}$$

鉴于我每次都记错这个递推式，我要着重讲一下它的含义。

$\left\{\begin{array}{l}n-1 \\k-1\end{array}\right\}$ 表示把第 $n$ 个球单独放在新的第 $k$ 个盒子里。

$k\left\{\begin{array}{c}n-1\\k\end{array}\right\}$ 表示把第 $n$ 个球放在任意盒子里，并且此时盒子数量仍然是 $k$ 。

可能写的有点奇怪，但是熟悉递推的同学应该知道我在说什么吧。

---

第一类斯特林数

第一类斯特林数记作 $s(n,k)$ 或 $\left[\begin{array}{l}n \\k\end{array}\right]$ 。

表示将 $n$ 个两两不同的元素划分为 $k$ 个互不区分的非空轮换的方案数。

换个说法，$n$ 个不同的数恰好划分为 $k$ 个圆排列的方案数

边界：

$$\left[\begin{array}{l}n \\0\end{array}\right] = [n=0]$$

递推式：

$$\left[\begin{array}{l} n \\ k \end{array}\right]=\left[\begin{array}{l} n-1 \\ k-1 \end{array}\right]+(n-1)\left[\begin{array}{c} n-1 \\ k \end{array}\right]$$

---

伯努利数

常用于等幂求和（ $m$ 次幂和的公式）

记 $S_m(n) = \sum\limits_{i=0}^{n-1} i^m$ ，则

$$S_m(n) = \dfrac{1}{m+1} \sum_{k=0}^{m} \dbinom{m+1}{k} B_kn^{m+1-k}$$

其中 $B_k$ 为伯努利数，定义如下

$$B_0 = 1\\ \sum_{j=0}^{m}\dbinom{m+1}{j}B_j = 0,\quad m>0$$

例如 $\binom{2}{0} B_0 = \binom{2}{1}B_1 = 0$

$n$	0	1	2	3	4	5	6	7	$\dots$
$B_n$	$1$	$-\frac{1}{2}$	$\frac{1}{6}$	$0$	$-\frac{1}{30}$	$0$	$\frac{1}{42}$	$0$	$\dots$

代码求解

咕咕咕…

---

贝尔数（Bell数）

$B_n$ 是基数为 $n$ 的集合的划分方法的数目

集合 $S$ 的一个划分定义为 $S$ 的两两不相交的非空子集的族，它们的并为 $S$

例如 $B_3=5$ ，因为 $3$ 个元素的集合 $a,b,c$ 有 $5$ 种不同的划分方法

$$\{ \{ a \}, \{ b \}, \{ c \} \} \\ \{ \{ a \}, \{ b,c \} \} \\ \{ \{b \}, \{ a,c \} \} \\ \{ \{ c \}, \{ a,b \} \} \\ \{ \{ a,b,c \} \}$$

贝尔数适合递推公式

$$B_0=B_1=1\\\\ B_{n+1} = \sum_{k=0}^{n}\dbinom{n}{k}B_k,\quad n \ge 1$$

贝尔三角形（类似于杨辉三角）

$$\begin{matrix} 1\\ 1&2\\ 2&3&5\\ 5&7&10&15\\ 15&20&27&37&52\\ 52&67&87&114&151&203\\ \end{matrix}$$ $$A_{i,j} = \begin{cases} 1, &i=1\land j=1 \\\\ A_{i-1,j-1}, &i\ne 1 \land j=1 \\\\ A_{i,j-1}+A_{i-1,j-1}, &i\ne 1 \land j \ne 1 \end{cases}$$

则有 $B_n = A_{n,1}$

代码求解

咕咕咕….