排列组合的定义

排列

从 $n$ 个不同元素中，任取 $m$ 个不同的元素按照一定的顺序排成一列，所有可能的情况种数叫做排列数，记作 $A_n^m$。

组合

从 $n$ 个不同元素中，任取 $m$ 个元素并成一组，所有可能的情况种数叫做组合数，记作 $C_n^m$，也记作 $\dbinom{n}{m}$

对于二者的区别最直观的理解就前者考虑顺序，而后者不考虑。

加法原理

做一件事，完成它可以有 $n$ 类方法，在第一类方法中有 $m1$ 种不同方法，在第二类方法中有 $m_2$ 种不同方法，……，在第 $n$ 类方法中有 $m_n$ 种不同方法，那么完成这件事共有 $\sum{i=1}^n m_i$ 种不同的方法。

乘法原理

做一件事，完成它需要分成 $n$ 个步骤，做第一步有 $m1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法，……，做第 $n$ 步有 $m_n$ 种不同的方法。那么完成这件事共有 $\prod{i=1}^n m_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;
    }

    范德蒙德卷积

    组合意义：在一个大小为 $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$ 个相同的盒子，一种球可以用多次，把盒子塞满，有多少种方案？

    不相邻组合

    有 $m$ 个球，$n$ 个盒子，选出的球不能相邻，有多少种组合方式？

    格路模型

    从坐标原点走到 $(n,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$，再把它加回去，
    总的式子就是
    将这个规律推广，也类似这样一加一减交替，这就是容斥原理。

    斯特林数

    第二类斯特林数

    表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。记作 $S(n,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,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$。
公式：

边界：