排列组合的定义

排列

从 \(n\) 个不同元素中，任取 \(m\) 个不同的元素按照一定的顺序排成一列，所有可能的情况种数叫做排列数，记作 \(A_n^m\)。 \[A_n^m=\frac{n!}{(n-m)!}\] #### 组合 从 \(n\) 个不同元素中，任取 \(m\) 个元素并成一组，所有可能的情况种数叫做组合数，记作 \(C_n^m\)，也记作 \(\dbinom{n}{m}\) \[C_n^m=\binom{n}{m}=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\] 对于二者的区别最直观的理解就前者考虑顺序，而后者不考虑。 #### 加法原理 做一件事，完成它可以有 \(n\) 类方法，在第一类方法中有 \(m_1\) 种不同方法，在第二类方法中有 \(m_2\) 种不同方法，……，在第 \(n\) 类方法中有 \(m_n\) 种不同方法，那么完成这件事共有 \(\sum_{i=1}^n m_i\) 种不同的方法。 #### 乘法原理 做一件事，完成它需要分成 \(n\) 个步骤，做第一步有 \(m_1\) 种不同的方法，做第二步有 \(m_2\) 种不同的方法，……，做第 \(n\) 步有 \(m_n\) 种不同的方法。那么完成这件事共有 \(\prod_{i=1}^n m_i\) 种不同的方法。 ### 二项式定理 \[(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}\] 变形： \[(a-b)^n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}a^ib^{n-i}\] \[\frac{(a+b)^n+(a-b)^n}{2}=\sum_{i为偶数}^n\binom{n}{i}a^{n-i}b^i\] 性质： - 杨辉三角与二项式系数有对应关系，所以根据杨辉三角的性质，我们可以得到递推关系：\(\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\)。 - 在 \(n\) 个里面选 \(k\) 个，就相当于不选 \(n-k\) 个，这与选 \(n-k\) 个相等，\(\dbinom{n}{k}=\dbinom{n}{n-k}\)。 - 令 \(a=b=1\)，\(2^n=\sum_{i=0}^n\dbinom{n}{i}\)。 - \(\sum_{i为奇数}\dbinom{n}{i}=\sum_{i为偶数}\dbinom{n}{i}=2^{n-1}\) ### 快速计算组合数的方法 - 预处理逆元，定义法计算 

1
2
3
4
5
6
7
8
9
10
11
12
void init(){
	fact[0]=1;
	for(int i=1;i<=n;i++)
		fact[i]=fact[i-1]*i%mod;
	inv_fact[n]=qpow(fact[n],mod-2,mod);//费马小定理，当然也可以用其他方式
	for(int i=n-1;i>=0;i--)
		inv_fact[i]=inv_fact[i+1]*(i+1)%mod;
	return;
}
long long comb(int n,int k){
	return fact[n]*inv_fact[k]%mod*inv_fact[n-k]%mod;
}
- 将杨辉三角打表 - 模数较小的时候使用 Lucas 定理和 exLucas 定理 Lucas 定理 \(\dbinom{n}{k}=\dbinom{n\bmod p}{k\bmod p}\times \dbinom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}\)，可以持续展开。注意，\(p\) 必须是质数。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int qpow(int a,int b,int mod){
	a%=mod;
	int res=1;
	while(b){
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int C(int n,int m,int p){
	if(m>n)
		return 0;
	if(m>n-m)
		m=n-m;
	int a=1,b=1;
	for(int i=0;i<m;i++){
		a=(a*(n-i))%p;
		b=(b*(i+1))%p;
	}
	return a*qpow(b,p-2,p)%p;
}
int lucas(int n,int m,int p){
	if(m==0) return 1;
	return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
### 范德蒙德卷积 \[\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\] 组合意义：在一个大小为 \(n+m\) 的集合中取出 \(k\) 个数，可以等于把大小为 \(n+m\) 的集合拆成两个集合，大小分别为 \(n\) 与 \(m\)，然后从 \(n\) 中取出 \(i\) 个数，从 \(m\) 中取出 \(k-i\) 个数的方案数。由于我们有了对于 \(i\) 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。 变式： - \(\sum_{i=1}^n\dbinom{n}{i}\dbinom{n}{n-1}=\dbinom{2n}{n-1}\) - \(\sum_{i=0}^n{\dbinom{n}{i}}^2=\dbinom{2n}{n}\) - \(\sum_{i=0}^m\dbinom{n}{i}\dbinom{m}{i}=\dbinom{n+m}{m}\) ### 隔板法 模型一：将 \(n\) 个相同苹果放入 \(m\) 个不同的箱子里的方案数（可以限制是否为空）。 考虑箱子里至少放 \(1\) 个苹果的情况，将这 \(n\) 个苹果排成一列，形成 \(n-1\) 个空隙，在这 \(n-1\) 个空隙中插入 \(m-1\) 个板子，就形成了一种解。所以解为 \(\dbinom{n-1}{m-1}\)。 箱子可以为空时解为 \(\dbinom{n-1+m}{m-1}\)，假设每个箱子里多出了一个虚拟苹果，我们就又回到了刚才的问题。 模型二：求方程 \(x_1+x_2+\cdots+x_m=n\) 的正整数解或自然数解的方案数。 变式：上式中 \(=\) 变为 \(\le\) 或 \(<\)，我们可以虚拟一个 \(x_0\) 令其加上后面的 \(x\) 等于 \(n\)。 ### 一些模型 #### 可重组合 有 \(m\) 种球，每种球足够多，\(n\) 个相同的盒子，一种球可以用多次，把盒子塞满，有多少种方案？\[\binom{m+n-1}{m}\] #### 不相邻组合 有 \(m\) 个球，\(n\) 个盒子，选出的球不能相邻，有多少种组合方式？\[\binom{n-m+1}{m}\] #### 格路模型 从坐标原点走到 \((n,m)\)，每次只能向右或向上移动，方案数是\[\binom{n+m}{n}=\binom{n+m}{m}\] ### 容斥原理 引入：有 \(n\) 个人，都参加过 WC、CTSC 和 APIO。问拿过至少一个比赛金牌的有多少人。 首先我们定义 \(3\) 个集合 \(A\)，\(B\)，\(C\)，分别表示在这三个比赛中拿过金牌的人，显然我们可以画出 Venn 图 image 首先，我们把 \(A\)，\(B\)，\(C\) 的元素数相加，显然多算了集合之间的交集，然后我们减去 \(A\cap B\)，\(B\cap C\)，\(A\cap C\) 的元素数，我们发现多减了 \(A\cap B\cap C\)，再把它加回去， 总的式子就是\[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|\] 将这个规律推广，也类似这样一加一减交替，这就是容斥原理。 ### 斯特林数 #### 第二类斯特林数 表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空子集的方案数。记作 \(S(n,k)\)， 递推式 \[S(n,k)=S(n−1,k−1)+k⋅S(n−1,k)\] 边界条件： - \(S(n,n)=1\)（每个元素单独成一个子集）。 - \(S(n,1)=1\)（所有元素放在一个子集中）。 - \(S(n,k)=0\) 当 \(k>n\) 或 \(k=0\) 且 \(n>0\)。 #### 第一类斯特林数 示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空轮换的方案数。记作 \(s(n,k)\)，递推式 \[s(n,k)=s(n−1,k−1)+(n−1)⋅s(n−1,k)\] 边界条件； - \(s(n,n)=1\)（每个元素单独成一个轮换）。 - \(s(n,1)=(n-1)!\)（所有元素放在一个轮换中）。 - \(s(n,0)=0\) 当 \(n>0\)。 ### 卡特兰数 - 一个栈（无穷大）的进栈序列为 \(1,2,3, \cdots ,n\) 有多少个不同的出栈序列？ - 有一个大小为 \(n\times n\) 的方格图左下角为 \((0, 0)\) 右上角为 \((n, n)\)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 \(y=x\) 上方（但可以触碰）的情况下到达右上角有多少可能的路径？ - 由 \(n\) 对括号组成的合法序列的数量。

这些问题的答案都是卡特兰数列 \(H_n\)。 公式： \[H_n=\frac{\binom{2n}{n}}{n+1}\] \[H_n=\binom{2n}{n}-\binom{2n}{n-1}\] 边界： \[H_0=H_1=1,H_2=2,H_3=5,H_4=14,\cdots\]