CloudySky

纵使世界万般残酷

总有温暖值得守护

排列组合 学习笔记

组合数学是 OI 数学中的一个重要分支。在 OI 中有很多用途。具体包含排列，组合，以及衍生出来的特殊排列组合，和一些特殊的依托于组合数数列，如：卡特兰数，斯特林数等以及一些计数问题。

警告⚠：这篇博客里包含了大量的概念性用语，请注意梳理大脑信息。这里的证明有一些不是很严谨的地方和感性理解（换句话说，写了证明两个字并不一定真的在证明）。

加法原理与乘法原理

比较容易理解，完成一件事，有 nn 类方法互不干扰，每类有 aia_i 种，方案数即为 ∑ai\sum a_i ；有 nn 个步骤互不干扰，每个步骤有 aia_i 种，方案数为 ∏ai\prod a_i 。

排列组合公式

组合

CnmC^m_n 代表从 n 个数中选出 m 个元素组成集合。

Cnm(也可以写作(nm))=n!(n−m)!m!C_n^m(\text{也可以写作}\dbinom{n}{m})=\dfrac{n!}{(n-m)!m!}

组合数的性质（二项式推论）以及证明和应用

有些东西可能和后面有交叉。

(nm)=(nn−m)(1)\dbinom{n}{m} = \dbinom{n}{n - m} \tag{1}

(1) 又称对称恒等式，感性理解即可，从 nn 个里面选 mm 个组成集合，那么剩下 n−mn - m 个自然构成另一个集合。

(nk)=nk(n−1k−1)(2)\dbinom{n}{k} = \dfrac{n}{k}\dbinom{n - 1}{k - 1} \tag{2}

(2) 由定义式直接推导出即可。

(nm)=(n−1m)+(n−1m−1)(3)\dbinom{n}{m} = \dbinom{n - 1}{m} + \dbinom{n - 1}{m - 1} \tag{3}

(3) 增量法。从 nn 个数里选 mm 个，可以分成两种方法，

  1. 选第 mm 个，在剩下的 n−1n - 1 个数中选 m−1m - 1 个。
  2. 不选第 mm 个，在剩下的 n−1n - 1 个数中选 mm 个。

组合数的递推式，可以 O(n2)O(n^2) 求组合数。

∑i=0k(ni)(mk−i)=(m+nk)(n,m≥k)(4)\sum_{i = 0}^k \dbinom{n}{i}\dbinom{m}{k - i} = \dbinom{m + n}{k} (n, m \ge k)\tag{4}

(4) 范德蒙公式。可以感性理解，从 n+mn + m 个方案中选 mm 个，可以分成两组，大小分别为 nn 和 mm ，从两组里共选 mm 个。可以分别从两组里选 xx 个和 yy 个，使得 x+y=mx + y = m 。

可以用来合并组合数，降低复杂度。也可以反向使用，方便数据结构维护。

拓展式：

∑i=0m(ni)(mi)=∑(ni)(mm−i)=(n+mm)\sum_{i = 0}^m \dbinom{n}{i} \dbinom{m}{i} = \sum\dbinom{n}{i}\dbinom{m}{m - i} = \dbinom{n + m}{m}

(nr)(rk)=(nk)(n−kr−k)(5)\dbinom{n}{r}\dbinom{r}{k} = \dbinom{n}{k}\dbinom{n - k}{r - k} \tag{5}

(5) **重要！**根据定义求，暴力推阶乘即可。

(nr)(rk)=n!(n−r)!⋅(r−k)!⋅k!=n!k!⋅(n−k)!(n−k)!(n−r)!(r−k)!=(nk)(n−kr−k)\dbinom{n}{r}\dbinom{r}{k} = \dfrac{n!}{(n - r)!\cdot (r - k)! \cdot k!} \\ = \dfrac{n!}{k!\cdot (n - k)!} \dfrac{(n - k)!}{(n - r)! (r - k)!} = \dbinom{n}{k} \dbinom{n - k}{r - k}

经典的应用：交换求和顺序，化简来降低复杂度：

∑k=0∑i=0f(i)⋅(nk)(ki)=∑if(i)(ni)∑k(n−ik−i)=∑if(i)(ni)⋅2n−i\sum_{k = 0}\sum_{i = 0} f(i)\cdot \dbinom{n}{k} \dbinom{k}{i} = \sum_{i} f(i) \dbinom{n}{i} \sum_{k} \dbinom{n - i}{k - i} = \sum_{i} f(i) \dbinom{n}{i} \cdot 2^{n - i}

∑i=0n(lk)=(n+1k+1)(6)\sum_{i = 0}^n \dbinom{l}{k} = \dbinom{n + 1}{k + 1} \tag{6}

(6) **重要！**可以通过组合意义证明。实质上是 (3) 的变形。首先 ∑i=0k−1\sum_{i = 0}^{k - 1} 是无效的。

考虑从 n+1n + 1 个数选择 k+1k + 1 个，相当于枚举第一个被选择的数是第几个。

∑i=0k(ni)=2⋅∑i=0k(n−1i)−(nk)(7)\sum_{i = 0}^k \dbinom{n}{i} = 2\cdot \sum_{i = 0}^k \dbinom{n - 1}{i} - \dbinom{n}{k} \tag{7}

(7) 同样是一个非常重要的公式，可以根据 (3) 推导出来

∑i=0n(−1)i(ni)=0 (n≠0)(8)\sum_{i = 0}^n(-1)^i\dbinom{n}{i} = 0\ (n \ne 0)\tag{8}

(8) 反演公式。二项式定理的特殊形式，令 a=1,b=−1a = 1, b = -1 套公式即可。

∑i=1n(ni)=2n(9)\sum_{i = 1}^n \dbinom{n}{i} = 2^n \tag{9}

(9) 同样可以用二项式定理来证： 2n=(1+1)n=∑(ni)2^n = (1 + 1) ^ n = \sum \dbinom{n}{i}

∑i=0ni(ni)=n⋅2n−1(10)\sum_{i = 0}^n i \dbinom{n}{i} = n\cdot 2^{n - 1} \tag{10}

(10) 对 (9) 求导可得。

警告⚠：以下过程为大佬讲解但一懂半懂的内容，可能会有错误：

对(ni)求生成函数得∑(ni)⋅xi则i⋅(ni)生成函数的积分为x∑(ni)⋅xi后面的部分化简一下为x(1+x)n对上面的东西求导，则为n⋅x⋅(1+x)n−1求和就相当于代入x=1则为n⋅2n−1对 \dbinom{n}{i} 求生成函数得 \sum\dbinom{n}{i}\cdot x^i \\ 则 i\cdot\dbinom{n}{i} 生成函数的积分为 x\sum\dbinom{n}{i}\cdot x^i \\ 后面的部分化简一下为 x(1 + x)^n \\ 对上面的东西求导，则为 n\cdot x \cdot (1 + x)^{n - 1} \\ 求和就相当于代入 x = 1 则为 n\cdot2^{n - 1}

或者：

∑i=0ni⋅(ni)=i⋅n!i!⋅(n−i)!=n⋅(n−1)!(i−1)!⋅(n−i)!=∑i=0nn⋅(n−1i−1)=n⋅2n−1\sum_{i = 0}^ni \cdot \dbinom{n}{i} = \dfrac{i\cdot n!}{i!\cdot (n - i)!} = \dfrac{n\cdot (n - 1)!}{(i - 1)! \cdot (n - i)!} = \sum_{i = 0}^n n \cdot \dbinom{n - 1}{i - 1} = n\cdot 2^{n - 1}

∑i=0ni2⋅(ni)=n⋅(n+1)⋅2n−2(11)\sum_{i = 0}^n i^2\cdot \dbinom{n}{i} = n\cdot (n + 1)\cdot2^{n - 2} \tag{11}

(11) 在 (10) 的基础上再求一个导。

∑i=0n(n−ii)=Fn+1(12)\sum_{i = 0}^n \dbinom{n - i}{i} = F_{n + 1} \tag{12}

(12) 组合数和斐波那契数列的联系，证明不会。

不相邻组合

从 nn 个数里面选 kk 个，任意两个数不相邻的方案数 (n−k+1k)\dbinom{n - k + 1}{k} 。

证明：

设 d1,d2,⋯ ,dkd_1, d_2, \cdots, d_k 是一组不相邻组合，令 d1<d2<⋯<dk,c1=d1,c2=d2−1,⋯ ,ck=dk−k+1d_1 < d_2 <\cdots < d_k, c_1 = d_1, c_2 = d_2 - 1, \cdots, c_k = d_k - k + 1 ，易知 c1<c2<⋯<ck<n−k+1c_1 < c_2 < \cdots < c_k < n - k + 1 。反之亦然。则 dd 与 cc 构成充要条件。所以选择 dd 的方案数和选择 cc 的方案数等价。

多重集的组合数

设广义集合 S=n1⋅ai,n2⋅a2,⋯ ,nk⋅akS = {n_1\cdot a_i, n_2\cdot a_2, \cdots, n_k\cdot a_k} 由 n1n_1 个 a1a_1 ，n2n_2 个 a2a_2 ，⋯\cdots ， nkn_k 个 aka_k 构成。则从 SS 里选 rr 个数的方案数常表示为:

∑r1+r2+⋯+rk=r(nr1,r2,⋯ ,rk)\sum_{r_1 + r_2 + \cdots + r_k = r}\dbinom{n}{r_1, r_2, \cdots, r_k}

具体情况有两种：

  1. r≤min⁡i=1knir \le \min_{i = 1}^k n_i ，方案数为 (r+k−1k−1)\dbinom{r + k - 1}{k - 1} 。

    证明用隔板法即可。考虑这个东西可以理解成 kk 个盒子放 rr 个球，可空。令 n1′=n1+1,n2′=n2+1,⋯ ,nk′=nk=1n_1' = n_1 + 1, n_2' = n_2 + 1, \cdots, n_k' = n_k = 1 ，方程就变成了 x1′+x2′+⋯+xk′=r+kx_1' + x_2' + \cdots + x_k' = r + k ，相当于在 kk 个盒子放 r+kr + k 个球，不可空，这样就可以隔板了。方案数为在 r+k−1r + k - 1 个空隙中插入 k−1k - 1 个板的方案数，即为 (r+k−1k−1)\dbinom{r + k - 1}{k - 1} 。

  2. r>min⁡i=1knir > \min_{i = 1}^k n_i ，要用到容斥。可以转换成不定方程非负整数解计数问题。因为这是一个求交集的问题，所以可以转化成求补集的并集。

    Ans=∑S⊆Uk(−1)∣S∣(k+r−1−∑i∈S(ni+1)k−1)Ans =\sum_{S \subseteq U}^k(-1)^{|S|}\dbinom{k + r - 1 -\sum_{i\in S} (n_i + 1)}{k - 1}

排列

PnmP^m_n 代表从 n 个数中选出 m 个元素组成排列（排列是有序的）。

Pnm=n!(n−m)!P^m_n=\dfrac{n!}{(n-m)!}

圆排列

圆排列就是增加了循环同构的性质，即 1 2 3 和 2 3 1 是一样的。结论 Pnm′=PnmmP_n^{m'}=\dfrac{P_n^m}{m} ,即 pnm=n!(n−m)!mp_n^m=\dfrac{n!}{(n-m)!m}

全错位排列

满足 ∀i∈[1,n],pi≠i\forall i \in [1,n], p_i \ne i 的排列叫做全错位排列。

Pn={0n=11n=2(n−1)(Pn−1+Pn−2)n≥3P_n=\begin{cases} 0&n=1\\ 1&n=2\\ (n-1)(P_{n-1}+P_{n-2})&n\ge 3\end{cases}

证明：增量法。

设已经排好了 n−1n - 1 个数，现在要加入第 nn 个数，能对当前排列数造成贡献的有两类情况。

  1. 前面全错位，这个时候和前面任意一项交换即可。共有 n−1n - 1 种转移方法。

  2. 前面有一项 xx 没有错位，这个时候相当于有 n−2n - 2 项满足条件，第 nn 项必须和 xx 交换。xx 一共有 n−1n - 1 种情况，每种情况只有 1 种转移方法。

综上所述 Pn=(n−1)(Pn−1+Pn−2)P_n = (n - 1)(P_{n - 1} + P_{n - 2})

错位排列

P(n,m)=(n−m)P(n−1,m)+mP(n−1,m−1)P(n , m) = (n - m)P(n - 1, m) + mP(n - 1, m - 1)

证明和上面类似

多重集的排列数

设广义集合 S=n1⋅ai,n2⋅a2,⋯ ,nk⋅akS = {n_1\cdot a_i, n_2\cdot a_2, \cdots, n_k\cdot a_k} 由 n1n_1 个 a1a_1 ，n2n_2 个 a2a_2 ，⋯\cdots ， nkn_k 个 aka_k 构成。则它的排列数为：

n!∏i=1kni!\dfrac{n!}{\prod_{i = 1}^k n_i !}

类似容斥？把重复的地方扣掉了。

二项式定理

(a+b)=∑k=0nCnkakbn−k(a + b) = \sum ^n_{k=0}C_n^k a^k b^{n-k}

证明：

考虑数学归纳法：

  • 当 n=1n = 1 时，(a+b)1=Cn0a0b1+Cn1a1b0=a+b(a + b)^1 = C_n^0 a^0 b^1 + C_n^1 a^1 b^ 0 = a + b 是显然成立的。

  • 假设当 n=kn = k 时成立，那么当 n=k+1n = k + 1 时：

    (a+b)(a+b)k=(a+b)∑i=0k(ki)aibk−i=∑i=0k(ki)ai+1bk−i+∑i=0k(ki)aibk−i+1=∑i=1k+1(ki−1)aibk−i+1+∑i=0k(ki)aibk−i+1=∑i=0k+1(k+1i)aibk+1−i(a + b)(a + b)^k = (a + b)\sum_{i = 0} ^ k \dbinom{k}{i} a^i b^{k - i} \\ = \sum_{i = 0}^k \dbinom{k}{i} a^{i + 1} b^{k - i} + \sum_{i = 0} ^ k \dbinom{k}{i} a^i b^{k - i + 1} \\ = \sum_{i = 1}^{k + 1}\dbinom{k}{i - 1} a^i b^{k - i + 1} + \sum_{i = 0} ^ k \dbinom{k}{i} a^i b^{k - i + 1} \\ = \sum_{i = 0}^{k + 1}\dbinom{k + 1}{i} a^i b^{k + 1 - i}

    证毕。

多项式形式：

(x1+x2+⋯+xk)n=∑n1+n2+⋯+nk=n(nn1,n2,⋯ ,nk)x1n1x2n2⋯xknk(x_1 + x_2 + \cdots + x_k)^n = \sum_{n_1 + n_2 + \cdots + n_k = n}\dbinom{n}{n_1, n_2, \cdots, n_k} x_1^{n_1} x_2^{n_2}\cdots x_k^{n_k}

Lucas 定理

Cnm mod p=Cn/pm/p×Cn  mod pm  mod p mod pC_n^m \bmod p=C_{n/p}^{m/p}\times C_{n\ \bmod p}^{m\ \bmod p} \bmod p

一般用来化简项数过高的组合数。

线性求组合数

求组合数可以用 (3) 来进行 n2n^2 递推，但是复杂度不够优秀，所以需要线性求阶乘以及阶乘逆元用定义式来求组合数。

代码实现： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long long jc[Maxn], jc_inv[Maxn], inv[Maxn], P;

void init (long long n) {
  jc[0] = jc[1] = 1, jc_inv[0] = jc_inv[1] = 1, inv[1] = 1;
  for (long long i = 2; i <= n; ++i) {
    jc[i] = jc[i - 1] * i % P;
    inv[i] = (P - P / i) * inv[P % i] % P;
    jc_inv[i] = jc_inv[i - 1] * inv[i] % P;
  }
}

long long C (long long n, long long m) {
  if (n < m) return 0;
  return jc[n] * jc_inv[m] % P * jc_inv[n - m] % P;
}

long long Lucas (long long n, long long m) {
  if (m == 0) return 1;
  return C(n % P, m % P) * Lucas (n / P, m / P) % P;
}

本文作者：CloudySky
写作时间： 2022-01-20
最后更新时间： 2022-01-20
遵循协议： BY-NC-SA

Top