组合计数学习笔记

发表于 更新于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

这个 PPT 里面的内容更完善

Part 1. 计数原理

加法原理和乘法原理是组合数学中最基础的计数原理。

加法原理

完成一个工程有 nn 类办法，aia_i (1≤i≤n)(1\leq i\leq n) 代表第 ii 类方法的数目。那么完成这件事共有 S=a1+a2+⋅⋅⋅+anS=a_1+a_2+\cdot\cdot\cdot +a_n 种不同的方法。

乘法原理

完成一个工程需要分 nn 个步骤，aia_i (1≤i≤n)(1\leq i\leq n) 代表第 ii 个步骤的不同方法数目。那么完成这件事共有 S=a1×a2×⋅⋅⋅×anS=a_1\times a_2\times \cdot\cdot\cdot\times a_n 种不同的方法。

练习（后两题有一定难度）：

P8557 炼金术（Alchemy）

P5303 逼死强迫症

P8321 『JROI-4』沈阳大街 2

抽屉原理

抽屉原理，亦称鸽巢原理（the pigeonhole principle)。

它常被用于证明存在性证明和求最坏情况下的解。是交互题中常见的方法。

其最简单情况为：将 n+1n+1 个物体划分为 nn 组，则至少有一组有两个（或以上）的物体。

证明：假如每个分组有至多 11 个物体，那么最多有 1×n1\times n 个物体，而实际上有 n+1n+1 个物体，矛盾。

Part 2. 组合数

从 nn 个不同的元素中，任取 mm (m≤n)(m\leq n) 个元素组成一个组合。那么从 nn 个不同元素中取出 mm (m≤n)(m\leq n) 个元素的所有组合的个数，叫做从 nn 个不同元素中取出 mm 个元素的组合数。用符号 CnmC_n^m 或 (nm)\tbinom{n}{m} 表示（由于后者书写起来更加清晰简洁，因此现在数学界普遍采用后者）

特别地，当 m>nm>n ，(nm)=0\tbinom{n}{m}=0 。

组合数通项公式：

(nm)=n!m!(n−m)!=nm‾m!\tbinom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{n^{\underline{m}}}{m!}

递推式：

(nm)=(n−1m−1)+(n−1m)\tbinom{n}{m}=\tbinom{n-1}{m-1}+\tbinom{n-1}{m}

Lucas 定理

(nm) mod p=(n mod pm mod p)⋅(⌊n/p⌋⌊m/p⌋) mod p\tbinom{n}{m}\bmod p=\tbinom{n \bmod p}{m \bmod p}\cdot\tbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\bmod p

其中，pp 为素数。

证明较为复杂，直接把结论记下来就行了

二项式定理

(a+b)n=∑i=0n(ni)aibn−i(a+b)^n=\sum\limits_{i=0}\limits^n \tbinom{n}{i}a^ib^{n-i}

证明显然，略。

组合恒等式

建议提前画出杨辉三角来辅助理解下面内容。

行求和

∑i=0n(ni)=2n\sum\limits_{i=0}\limits^n \tbinom{n}{i}=2^n

证明：考虑二项式定理 a=b=1a=b=1 的情况

∑i=0n(−1)i(ni)=0\sum\limits_{i=0}\limits^n (-1)^i \tbinom{n}{i}=0

证明：考虑二项式定理 a=1a=1 , b=−1b=-1 的情况

列求和

∑i=0m(in)=∑i=nm(in)=(m+1n+1)\sum\limits_{i=0}\limits^m \tbinom{i}{n}=\sum\limits_{i=n}\limits^m \tbinom{i}{n} = \tbinom{m+1}{n+1}

证明：由于：

(nn)=(n+1n+1)=1\tbinom{n}{n}=\tbinom{n+1}{n+1}=1

因此 ：

(nn)+(n+1n)=(n+2n+1)\tbinom{n}{n}+\tbinom{n+1}{n}=\tbinom{n+2}{n+1}

(nn)+(n+1n)+(n+2n)=(n+3n+1)\tbinom{n}{n}+\tbinom{n+1}{n}+\tbinom{n+2}{n}=\tbinom{n+3}{n+1}

⋮\vdots

依此类推可知：

∑i=nm(in)=(m+1n+1)\sum\limits_{i=n}\limits^m \tbinom{i}{n} = \tbinom{m+1}{n+1}

吸收恒等式

描述 (nm)\tbinom{n}{m} 和 (n±1m±1)\tbinom{n\pm1}{m\pm1} 的关系（即邻项间的关系）

利用组合数的定义即可推出。

范德蒙德卷积

∑i=0k(ni)(mk−i)=(n+mk)\sum\limits_{i=0}\limits^k \tbinom{n}{i}\tbinom{m}{k-i}=\tbinom{n+m}{k}

组合意义：在一个大小为 n+mn+m 的集合中取出 kk 个数，可以等于把大小为 n+mn+m 的集合拆成两个集合，大小分别为 nn 与 mm ，然后从 nn 中取出 ii 个数，从 mm 中取出 k−ik-i 个数的方案数。由于我们有了对于 ii 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。

基础应用

隔板法

求 x1+x2+⋅⋅⋅+xn=mx_1+x_2+\cdot\cdot\cdot+x_n= m 的正整数解的个数

可以看成用 n−1n-1 个隔板把摆成一排的 mm 个物品分成 nn 段，那么问题就转化成了：在 m−1m-1 个空隙中选 n−1n-1 个空隙来插板，因此答案为：(m−1n−1)\tbinom{m-1}{n-1}

变式：求非负整数解个数

将问题转化为：

(x1+1)+(x2+1)+⋅⋅⋅+(xn+1)=m+n(x_1+1)+(x_2+1)+\cdot\cdot\cdot+(x_n+1)=m+n

然后就和上面一样了

格路计数（卡特兰数）

考虑一个网格图，每次可以向右或向上走一步，问从 (0,0)(0,0) 走到 (n,m)(n,m) 的方案数

一共要走 (n+m)(n+m) 步，其中有 nn 步是向右走，剩下 mm 步是向上走，因此答案为：(n+mn)\tbinom{n+m}{n}

变式：考虑一个网格图，每次可以向右或向上走一步，不能经过直线 y=x+1y=x+1 ，问从 (0,0)(0,0) 走到 (n,n)(n,n) 的方案数

答案即为卡特兰数

由于我懒得画图，所以这里贴出一个博客：

https://www.cnblogs.com/Morning-Glory/p/11747744.html

变式2：不能经过 y=x+b1y=x+b_1 和 y=x+b2y=x+b_2

和上面一样处理，再容斥一下就可以了（不会就算了，我已经容斥出阴影了）

错排数

有多少个 1∼n1\sim n 的排列 pp，满足 ∀i,pi≠i\forall i,p_i\neq i

Dn=(n−1)×Dn−2+(n−1)×Dn−1D_n=(n-1)\times D_{n-2}+(n-1)\times D_{n-1}

至于其组合意义，OI-Wiki 上已经讲得很清楚了：

https://oi-wiki.org/math/combinatorics/derangement/#递推的计算

练习

P2606 排列计数

P3773 吉夫特

P4071 排列计数

Part 3. 容斥原理

头疼警告

概念

设 UU 中元素有 nn 种不同的属性，而第 ii 种属性称为 PiP_i，拥有属性 PiP_i 的元素构成集合 SiS_i，那么

∣⋃i=1nSi∣=∑m=1n(−1)m−1∑ai<ai+1∣⋂i=1mSai∣\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|

应用

P3813 矩阵填数

未完待续……