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数学总结-数论]
#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\) 即可。
容斥原理的常用技巧：
定义一些“坏性质” \(P_1,\dots,P_m\)
找到对于每个 \(S\subseteq [m]\) 计算 \(N(S)\) 的方法
套用容斥原理计算不满足任何一个“坏性质”的元素个数
注意这里求的是不满足任何坏性质，因此用以下公式 \[ \sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right| \]
鸽巢原理（抽屉原理）
假如有 \(n+1\)个元素放到 \(n\) 个集合中去，其中必定有一个集合里至少有两个元素。
应用
- 任意 \(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}\)
代码求解
咕咕咕....
