by 木xx木大
组合计数
(一)基本计数原理
加法原理:
设集合 被划分成两两不相交的部分 。则 的对象数目可以通过确定它的每一个部分的对象数目并相加得到 ,即
乘法原理
设 为有序对 的集合,其中 来自一个大小为 的集合,而对于每个 , 有 种选择,则 。
实际上,乘法原理是加法原理的推论。
减法原理:
设 为全集, 是 的子集,则 中的对象数目 。
利用这一原理,我们可以用正难则反的思想解决问题。
(二)二项式系数
考虑 的展开,可以看作有 个物品,选这个物品看作 ,则选 个物品的方案数就对应最终的 次项系数,因此 ,这个结论被成为二项式定理,因此组合数也被称为二项式系数。
二项式定理也可表述为
常用恒等式
-
对称恒等式:
-
吸收/提取恒等式:
-
加法/归纳恒等式 :
组合意义:考虑枚举最后一个物品选不选
- 上指标求和:
组合意义:枚举从 个物品里选 个物品的最后一个物品
组合意义:从 个物品里选 个,再从这 个里面选 个,相当于直接从 个里面选 个,再从剩下的 个里面选 个
- 二项式定理的推论:
由以上两式可得
- 范德蒙德卷积:
组合意义:从数量为 和 的两堆物品中一共取 个物品。
用二项式定理解释其本质:
广义二项式定理
将二项式系数的上指标扩展到实数域上,就得到了广义二项式系数
相对应地,有广义二项式定理:
常用推论:
证明:
$$ \begin{aligned}(1+x){-n}&=\sum_{k=0}{\infty}{-n\choose k}xk\&=\sum_{k=0}{\infty}\frac{(-n)(-n-1)\dots(-n-k+1)}{k!}xk\&=\sum_{k=0}{\infty}(-1)k\frac{n(n-1)\dots(n+k-1)}{k!}xk\&=\sum_{k=0}{\infty}(-1)k{n+k-1\choose k}x^k\end{aligned}$$
(三)容斥原理
给定 个集合 ,如果我们可以方便地算出它们其中一些交集的大小,则可以推出它们并集的大小
$$
\begin{aligned} \left|\bigcup_{i=1}nS_i\right|=\sum_{T\subseteq[n]}n(-1)^{|T|+1}\left|\bigcap_{i\in T}S_{i}\right|
\end{aligned}
$$
其中 。这个式子的含义是:集合的并的大小可以通过枚举每一个子集,将子集内的集合求交并乘上 的子集大小加 1 次方求和得到。
证明:
容斥原理的另一种表述形式为(其实就是将上式取补集)
$$
\begin{aligned} \left|\overline{\bigcup_{i=1}nS_i}\right|=\sum_{T\subset[n]}n(-1)^{|T|}\left|\bigcap_{i\in T}S_{i}\right|\end{aligned}
$$
其中当 时后面部分定义为全集大小。
直观地理解, 件事至少有一件发生/均不发生的方案数可以通过其中每个子集同时发生的方案数计算。
子集反演
对于两个集合的函数 ,若,则
对于两个集合的函数 ,若,则
二项式反演
设 表示至多满足 个性质的方案数, 表示恰好满足 个性质的方案数,则有
$$
f(n)=\sum_{i=0}^n{n\choose i}g(i)\Rightarrow g(n)=\sum_{i=0}n(-1){n-i}{n\choose i}f(i)
$$
设 表示至少(钦定)满足 个性质的方案数, 表示恰好满足 个性质的方案数,则有
$$
f(n)=\sum_{i=n}^m{i\choose n}g(i)\Rightarrow g(n)=\sum_{i=n}m(-1){i-n}{i\choose n}f(i)
$$
根据上面两个式子,我们容易在 或 的复杂度内完成 的转化。容易发现,这两个式子和子集反演的本质是一样的。
经典应用:错排问题
设 表示恰好有 个数不在自己位置上的方案数。则有 ,套用二项式反演的第一个式子得到
例题:
P4491 [HAOI2018]染色
设 表示恰好有 种元素出现了 次的方案数, 表示钦定至少有 种元素出现了 次的方案数。则 ,二项式反演一下得到 ,其中 为可能出现的元素种类数,即 。二项式反演的式子是一个差卷积的形式, 优化即可。
题解 CF997C Sky Full of Stars
题解 P6478 [NOI Online #2 提高组]游戏
题解 P3270 [JLOI2016]成绩比较
Min-max 容斥
证明:
设 表示 中第 大的元素,当 时
- ,则 ,贡献为
- ,符合要求的 共有 种,且这些选法中 为奇数的占一半,贡献为 , 为偶数的占一半,贡献为 ,刚好抵消为 0
例题:
P3175 [HAOI2015]按位或
题解 P5643 [PKUWC2018]随机游走
扩展 Min-max 容斥
证明:
我们可以套用一般 Min−max 容斥的式子猜想 k 大值容斥的形式:
对于第 大的元素 ,只有仅包含它和比它大的元素的集合 才满足 ,这样的集合 共有 个,它的贡献系数为 。
令 ,二项式反演得到 ,即
例题:
题解 P4707 重返现世
综合练习
题解 P5400 [CTS2019]随机立方体
题解 P5405 [CTS2019]氪金手游
题解 P5644 [PKUWC2018]猎人杀
P5417 [CTSC2016]萨菲克斯·阿瑞(终极挑战!极其巧妙的映射转化!)
(四)特殊数和简单生成函数
卡特兰数
组合意义:
- 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数
- 个不同的数依次进栈,不同的出栈结果的种数
- 个节点的二叉树数量
- 从 到 的除端点外不穿过直线 的非降路径数
- 对括号的合法序列数
- ……
对于这些问题,我们容易得到一个暴力的递推式
但通常情况下,我们需要一个更优秀的式子,下面介绍几种推通项的方法。
若 是任意一个和为 1 的整数序列,则其所有循环位移中有且仅有一个满足所有前缀和都是正数。
证明:
每次必须取最后一个 前缀和的最小值 的后一位作为起点,使得其他最小值位置跨过序列结尾,前缀和为 1;否则如果有两个相等最小值而取前一个作为起点,第二个最小值位置前缀和是 0。
据此,假设 个数之和为 1,那么满足所有前缀和为正数的排列的数量即其圆排列的数量 ,因为每个圆排列(环)都只有一个链满足条件。设进栈为 1,出栈为 -1,问题转化为求有多少种由 个 1 和 个 -1 组成的序列满足任意前缀和
设进栈为 1,出栈为 -1,问题转化为求有多少种由 个 1 和 个 -1 组成的序列满足任意前缀和 。在序列最前面放一个 1 ,就可以应用 Raney 引理了。这样的圆排列数为。根据 Raney 引理,在一个循环同构的等价类中,只有一个串满足任意前缀和大于零,所以圆排列数即合法的排列数。因为第一位只能是 1 ,所以除去第一位后剩下部分的方案数也为
用类似方法做的例题:题解 P6672 [清华集训2016] 你的生命已如风中残烛
如果不考虑直线 的限制,则从 走到 的方案数为 。
任意一种非法方案都至少经过一个 的点 ,那么我们将这条路径 点以后的部分全部关于直线 对称,则任意一条非法路径都对应一条从 到 的路径。非法路径的条数为 ,则合法路径的条数为
用到类似方法做的例题:题解 P3266 [JLOI2015]骗我呢,AT2705 [AGC019F] Yes or No
设卡特数数列为 ,其生成函数为
其暴力递推形式非常像卷积,令 自卷
$$
\begin{aligned}
&(g(x))2=1+(h_0h_1+h_1h_0)x+(h_0h_2+h_1h_1+h_2h_0)x2\dots\
&xg(x)2=x+(h_0h_1+h_1h_0)x2+(h_0h_2+h_1h_1+h_2h_0)x^3\dots=g(x)-1\
&x(g(x))^2-g(x)+1=0\
&g(x)=\frac{1\pm\sqrt{1-4x}}{2x}
\end{aligned}
$$
将 代入,通过洛必达法则得
用广义二项式定理展开得
$$
\begin{aligned}
\sqrt{1-4x}=&\sum_{k=0}{\infty}\frac{\frac{1}{2}(\frac{1}{2}-1)\dots(\frac{1}{2}-k+1)}{k!}(-1)k4kxk\
=&1+\sum_{k=1}{\infty}\frac{(-1){k-1}}{2^k}\frac{(2k-2)!}{2\times 4\times\dots\times(2k-2) k!}(-1)k4kx^k\
=&1+\sum_{k=1}{\infty}\frac{(-1){k-1}}{2{2k-1}k}\frac{(2k-2)!}{((k-1)!)2}(-1)k4kx^k\
=&1+\sum_{k=1}^{\infty}\frac{(-2)}{k}{2k-2\choose k-1}x^k\
=&1-2\sum_{k=1}^{\infty}\frac{1}{k}{2k-2\choose k-1}x^k\
g(x)=\frac{1-\sqrt{1-4x}}{2x}
&=\sum_{k=1}^{\infty}\frac{1}{k}{2k-2\choose k-1}x{k-1}=\sum_{k=0}{\infty}\frac{1}{k+1}{2k\choose k}x^{k}\
\end{aligned}
$$
与上面用组合意义推出来的结果是一样的。
斯特林数
第一类斯特林数
定义第一类斯特林数 为 个元素分成 个圆排列的方案数。
递推公式:,组合意义即考虑新加入的元素单独成环或插入某个已有的环。
生成函数
对 的情况构造指数型生成函数
$$
S(x)=\sum_{i=0}(i-1)!\frac{xi}{i!}=\sum_{i=0}\frac{xi}{i}=-\ln(1-x)
$$
那么对于 为任意值的情况指数型生成函数即为
$$
\frac{S(x)m}{m!}=\frac{(-\ln(1-x))m}{m!}
$$
模板题:P5409 第一类斯特林数·列
第二类斯特林数
定义第二类斯特林数 为 个元素分成 个无序集合的方案数。
递推公式:,组合意义即考虑新加入的元素单独成一个集合或插入某个已有的集合。
生成函数
对 的情况构造指数型生成函数
$$
S(x)=\sum_{i=0}[i\ne 0]\frac{xi}{i!}=ex-1
$$
那么对于 为任意值的情况指数型生成函数即为
$$
\frac{S(x)m}{m!}=\frac{(ex-1))^k}{k!}
$$
模板题:P5396 第二类斯特林数·列
斯特林数与阶乘幂:
定义上升幂 ,定义下降幂
上升幂和下降幂可以互相转化:
组合意义: 即把 个物品放入 个有序集合中,允许存在空集的方案数。相当于先从 个集合中选出 个非空的,乘上 ;再把物品放进去,乘上 ;集合有序,再乘
推论:,推导如下
最后一步套用了上指标求和公式。这个式子常被用来解决自然数幂和问题。
例题:
P4827 [国家集训队] Crash 的文明世界
P4091 [HEOI2016/TJOI2016]求和
P6620 [省选联考 2020 A 卷] 组合数问题
题解 CF1097G Vladislav and a Great Legend
题解 CF932E Team Work
题解 CF1278F Cards
题解 CF961G Partitions
-
$\displaystyle {n\brace m}=\sum_{i=0}m\frac{(-1){m-i}i^n}{(m-i)!i!} $,对上面的式子二项式反演一下即可得到。可用来算 P5395 第二类斯特林数·行
-
斯特林反演
证明:
设 的 EGF 为 ,则有
代换一下得 ,展开得
\begin{aligned}
F(\ln(1+x))=&\sum_{k=0}F[k]\frac{(\ln(x+1))^k}{k!}\\=&\sum_{k=0}F[k]\frac{(-1)^k(-(\ln(1-(-x))))^k}{k!}\\=&\sum_{k=0}F[k](-1)^k\sum_{i=0}{k\brack i}\frac{(-x)^i}{i!}\\=&\sum_{i=0}\frac{x^i}{i!}\sum_{k=0}(-1)^{k-i}{k\brack i}F[k]\end{aligned}
比较一下系数即得
贝尔数
设 表示把 个元素划分到任意个无序非空集合的方案数。
通项:枚举划分出的集合的个数,得到
递推公式:考虑从原来的 个元素中选 个和第 个元素分到一个集合,得到
生成函数:生成单个集合的 EGF 为 ,那么贝尔数的 EGF 即为
模板题:P5748 集合划分计数
分拆数
分拆数有四种求法,你知道吗?
定义: 记 为将 拆分成若干无序正整数的和的方案数。
模板题:loj 6268。,答案对 998244353 取模。
例题:P6189 [NOI Online #1 入门组] 跑步(其实也是模板啦)
方法一
这个问题非常像完全背包。但 过不去。考虑根号分治:
-
对于小于 的数,暴力完全背包。
-
对于大于 的数,设 表示用了 个 的数,和为 的方案数,dp 一下,转移为 。前者表示加入一个 ,后者表示将现在的序列整体+1。
容易发现第一维大小只有 级别。
方法二
类似付公主的背包的做法。分拆数的 OGF 为
$$
P(x)=\prod_{k=1}\sum_{i=0}x{ik}=\prod_{k=1}\frac{1}{1-xk}=\exp\sum_{k=1}\ln\frac{1}{1-xk}=\exp\sum_{k=1}\sum_{i=1}\frac{x{ik}}{i}
$$
后面的求和可以 计算。具体见P4389 付公主的背包 题解
方法三
前置知识:五边形数
五边形数是能排成五边形的多边形数。
如图,前几项为 ,其通项公式为
广义五边形数: 可以取负数,其通项公式为
五边形数定理
定义欧拉函数
$$
\begin{aligned}
\phi(x)&=\prod_{i=1}(1-xi)\&=1-x-x2+x5+x7-x{12}-x{15}+\dots\
&=1+\sum\limits_{i=1}(-1)ix{i(3i\pm 1)/2}
\end{aligned}
$$
这条等式被称为五边形数定理。证明比较复杂,故不展开叙述。有兴趣的可以看 visit_world的博客
将 与 乘起来
$$
\begin{aligned} \phi(x)\sum_{k=0}{\infty}p(k)xk =& (1-x-x2+x5+x7-\ldots)\&(1+p(1)x+p(2)x2+p(3)x^3+\ldots)\ =& 1 \end{aligned}
$$
将整个式子展开,得到:
以内的五边形数是 级别的,所以递推式只有 项,于是我们得到了一个 的做法。
方法四
(图片来自百度百科)
前置知识:Ferrers diagram
一个分拆的 Ferrers 图,是把分拆出的每一项,用点(或方格)组成的行来表示。一般分拆写为递减正整数和,所以 Ferrers 图也用长度递减的行来表示。
Ferrers 图与分拆之间是一一对应的。如 14=6+3+3+2 的一个分拆的 Ferrers 图如下:
通过读它的列,得到的 Ferrers 图与原图互为共轭。
引申
-
对于所有行数不超过 的 Ferrers 图,都唯一对应一个列数不超过 的共轭图。因此整数 拆分成 个数的和的拆分数,和数 拆分成最大数为 的拆分数相等。
-
整数 拆分成最多不超过 个数的和的拆分数,和 拆分成最大不超过 的拆分数相等。
-
整数 拆分成互不相同的若干奇数的和的拆分数,和 拆分成自共轭的Ferrers图像的拆分数相等。例如:17=9+5+3
考虑从 Ferrers diagram 的原点引出一条 的直线,它离开这个图的位置就框处了一个 的正方形,这个正方形被称为一个整数拆分的 Durfee square。
如果我们确认了正方形的边长是 ,它两侧放置的就都是 的整数划分。因此我们得到了这样的表达式:
$$
\prod_{k\ge1} \frac1{1-x^k} = \sum_{h\ge0} x{h2} \left(\prod_{k=1}^h \frac1{1-xk}\right)2
$$
在计算前 项时,由于 ,枚举 的上界为 ,复杂度为 。
不会证的结论
- 对于 的分拆,各个分拆方案中出现至少 次的数的个数和,等于所有方案中 出现的总次数。详细见整数分拆中的一个出人意料的结论
- 对任意正整数,其奇分拆数目(每个部分均为奇数)等于其互异分拆(每个部分互不相同)数目。证明见《组合数学》
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:AFOI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用