「草稿」组合计数综合练习

常见数列

贝尔数：n 个数分成若干个非空集合的方案数

• $B_n=\sum_{k=0}^nS(n,k)$。
• 递推：$B_n=\sum_{k=0}^{n-1}\binom{n-1}{k}B_k$。

调和级数：$H_n=\sum_{i=1}^n\frac{1}{i}=\ln n+\varepsilon_n+\gamma$，其中$\gamma$是欧拉常数，$\varepsilon_n\approx \frac{1}{2n}$。

容斥原理

ARC 102 E

有 n 个不可取分的 k 面骰子，对于每个$i=2,3,\cdots,2K$，求有多少种方案使得：任意两个骰子朝上的面要么相同，要么和不为$i$。答案对$998244353$取模。

$2\le n\le 2000,1\le k\le 2000$。

先枚举$i$。也就是说$1,i-1$，$2,i-2$，……不能同时出现。那么就出现 0 次或者一次。直接枚举有多少组里出现了一个。假设有$j$组。设这$j$个有$2^j$种选择（左边或者右边）。然后考虑出现了多少次：$x_1+x_2+\cdots +x_j$，其中$x_i> 0$。然后枚举$y_i$表示比$i$大的数字出现的次数。把$x,y$放在一起插版即可。

集训队作业 2018 小 z 的礼物

设$t_x$表示 x 这个礼物第一次得到的时间。要求$E(\max t_x)$。考虑容斥。

$$\sum_{T\in S}(-1)^{|T|+1}E(\min_{x\in T}t_x)$$

$T$定下来：直接算随到一个的概率。假设有$X$个 pair 满足，一共有$Y$个 pair。那么期望就是$E(\min T)=\frac{Y}{X}$。

考虑 DP。$f(i,j,S,x)$表示现在考虑第$i$行第$j$个格子，$S$表示每行最后一个元素选不选。考虑$x$是否在子集中。

ARC 96 E Everything on It

题意：求有多少个子集族满足：

1. 其中任意一个子集都是$[n]$的子集；
2. 任意两个子集不同；
3. $1,2,\cdots,n$都在其中出现至少两次。

考虑容斥。枚举$i$表示$1,2,\cdots,i$出现次数小于等于$1$。那么答案为

$$\sum_i \binom{n}{i}(-1)^iF(i)$$

其中$F(i)$表示$1,\cdots i$出现次数小于等于 1 的方案数。

考虑枚举有$k$个集合含有$[1,i]$中至少一个，其他集合则不含有$[1,i]$。

显然不含有$[1,i]$的子集族数为$2^{2^{n-i}}$。

对于这个$k$个集合，我们考虑把$1,\cdots,i$分入$k$个集合，有的数字可以不放，每个数字最多出现一次。相当于再拿一个集合出来装垃圾。我们给垃圾堆强制加入数字$0$来保证每个集合非空。同时我们认为$0$所在的集合指向垃圾堆。这样就相当于是$i+1$个数分成$k+1$个非空集合，那么方案数就是$S(i+1,k+1)$。

至于这$k$个集合的其他数字则可以任意填，并且由于$k$个集合各种含有不同的$1,\cdots,i$的数字，因此其他部分就不需要考虑重复的问题了，那么方案数就是$(2^{n-i})^k$。

因此得到

$$F(i)=2^{2^{n-i}}\sum_k (2^{n-i})^kS(i+1,k+1)$$

ARC 101 E Ribbons on Tree

题意：给你一个 n 个点的数，其中 n 是偶数。问有多少种将$n$个点配成$n/2$对的方式，使得每对点的路径并覆盖了整棵树。$n\le 5000$。

不合法的情况就是某条边不被经过，相当于这条边被割掉。因此考虑容斥。暴力的做法是枚举被割掉的边集，然后每个连通块内无限制连边的方案数，复杂度$O(2^n)$。

首先考虑无限制连边的方案数。对于一个大小为$x$的连通块，它的配对方案数是

$$g(x)=\begin{cases} (x-1)(x-3)\cdots1 & x\equiv0\bmod 2\\ 0 & x\equiv 1\bmod 2 \end{cases}$$

那么考虑 DP 计算容斥贡献。设$f(i,j,0/1)$表示$i$的子树中，$i$所在连通块大小为$j$，被割的边数的奇偶性为$x$的配对方案数。注意，我们只统计被割掉的连通块的配对方案数，$i$所在的连通块暂不统计配对方案数。

假设$1$是根，我们要求的答案显然是

$$\sum_{i=1}^ng(i)(f(1,i,0)-f(1,i,1))$$

考虑转移，对于$(u\to v)$的边：

1. 不割。相当于把$v$所在的连通块接在$u$所在的连通块上。则$f(u,i)$和$f(v,j)$可以贡献到$f'(u,i+j)$上。
2. 割。则$f(u,i)$和$f(v,j)g(j)$贡献到$f'(u,i)$上。

对子树大小取 min，时间复杂度$O(n^2)$。

ARC 93 F

枚举$\{G_1,G_2,\cdots,g_n\}$的子集。要求$S$中的所有集合都满足最小值在$A$中，问方案数。记作$f(S)$。答案就是$\sum_S(-1)^{|S|}f(S)$。

从大到小考虑 A 中的元素。$dp(T)$表示$T$的最小值属于 A。

斯特林反演

下降幂：$n^{\underline{m}}=\prod _{i=0}^{m-1}(n-i)$。

通常幂转下降幂：$x^n=\sum_{k=0}^nS(n,k)x^{\underline{k}}$。

上升幂：$n^{\overline{m}}=\prod_{i=0}^{m-1}(n+i)$。

上升幂转通常幂：$x^{\overline{n}}=\sum_{k=0}^ns(n,k)x^k$。

反演公式

斯特林反演：

$$f(n)=\sum_{k=0}^nS(n,k)g(k)\\ g(n)=\sum_{k=0}^n(-1)^{n-k}s(n,k)f(k)$$

反转公式

$$\sum_{k=m}^n(-1)^{n-k}s(n,k)S(k,m)=[m=n]\\ \sum_{k=m}^n(-1)^{n-k}S(n,k)s(k,m)=[m=n]$$

引理：

$$x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}\\ x^{\overline{n}}=(-1)^{n}(-x)^{\underline{n}}$$

证明显然。

证明反转公式：

$$\begin{aligned} n^m&=\sum_{k=0}^mS(m,k)n^{\underline{k}}\\ &=\sum_{k=0}^mS(m,k)(-1)^k(-n)^{\underline{k}}\\ &=\sum_{k=0}^mS(m,k)(-1)^k\sum_{j=0}^ks(k,j)(-n)^{j}\\ &=\sum_{j=0}^mn^j\sum_{k=j}^mS(m,k)s(k,j)(-1)^{k-j} \end{aligned}$$

反之亦然。

证明反演公式：

$$\begin{aligned} f(n)&=\sum_{i=0}^n[i=n]f(i)\\ &=\sum_{i=0}^nf(i)\sum_{j=i}^nS(n,j)s(j,i)(-1)^{j-i}\\ &=\sum_{k=0}^nS(n,k)\sum_{i=0}^k(-1)^{k-i}s(k,i)f(i) \end{aligned}$$

也就是说如果$g$的定义式成立，那么$f$成立。

用另一个反转公式，那么如果$f$的定义式成立，那么$g$成立。这样就证完了。

2018 雅礼集训 方阵

给定$n\times m$的矩阵，每个格子填上$[1,c]$中的数字，求任意两行、两列均不同的方案数。

$n,m\le 5000$。

不同：对应位置不同。

考虑只要求行不相同。

设$g(m)$表示$m$列的矩阵，行互不相同的方案数。有$c^m$种可能的行。则

$$g(m)=(c^m)^{\underline{n}}$$

$f(m)$：$m$列的答案。枚举$g(m)$中列被分成多少类。

$$g(m)=\sum_{i=0}^mS(m,i)f(i)\\ f(m)=\sum_{i=0}^m(-1)^{m-i}s(m,i)g(i)$$

注：$f(0)=0$。

一道例题

给定 n 个结点的树，从某个点出发开始随机游走：在点 u 时，有$p_u$的概率留在原地，否则等概率向相邻结点移动，直到移动到 1 号点停下。求从每个结点出发直指停下，所花费的时间的 k 次方的期望。

$n\le 10^5,k\le 10^5,nk\le 10^6$。

设$u$到根结点的期望时间是$t_u$。我们要求$E(t_u^k)$。

$$\begin{aligned} E(t_u^k)&=E\left(\sum_{i=0}^kS(k,i)t_u^{\underline{i}}\right)\\ &=\sum_{i=0}^kS(k,i)i!E\left(\binom{t_u}{i}\right)\\ E\left(\binom{t_u}{i}\right)&=P_uE\left(\binom{t_u+1}{i}\right)+\frac{1-P_u}{d_u}\sum_{(u,v)}E\left(\binom{t_v+1}{i}\right)\\ E\left(\binom{t_u}{i}\right)&=P_uE\left(\binom{t_u}{i}+\binom{t_u}{i-1}\right)+\frac{1-P_u}{d_u}\sum_{(u,v)}E\left(\binom{t_v}{i}+\binom{t_v+1}{i-1}\right)\\ (1-P_u)E\left(\binom{t_u}{i}\right)&=P_uE\left(\binom{t_u}{i-1}\right)+\frac{1-P_u}{d_u}\sum_{(u,v)}E\left(\binom{t_v}{i}+\binom{t_v+1}{i-1}\right) \end{aligned}$$

考虑按照$i$从小到大的顺序做。设$E\left(\binom{t_u}{i}\right)=dp(u),E\left(\binom{t_u}{i-1}\right)=a_u$：

$$dp_u=P_u(dp_u+a_u)+\frac{1-P_u}{d_u}\sum_{(u,v)}(dp_v+a_v)\\ dp_u=\frac{P_ua_u}{1-P_u}+\frac{1}{d_u}\sum_{(u,v)}(dp_v+a_v)$$

可以按树上高消的套路做了。要记得$O(k\log_2k)$预处理斯特林数。

另一道例题

设连通块数为 T：$T^k=\sum_{i=0}^kS(k,i)i!\binom{T}{i}$。问题转化为求出$\sum_{T}\binom{T}{i}$，它表示选出了$i$个连通块。

设$dp_t(n)$表示 n 个点 t 个连通块的图的个数。

$$\sum_{T}\binom{T}{i}=\sum_{j=1}^n\binom{n}{j}dp_i(j)2^{\binom{n-j}{2}}\\ Ans=\sum_{i=0}^kS(k,i)i!n!\sum_{j=1}^ndp_i(n-j)\frac{1}{(n-j)!j!}2^{\binom{j}{2}}$$

问题转化为如何求$\frac{dp_i(j)}{j!}$。

$$dp_t(n)=\sum_{i=1}^n\binom{n-1}{i-1}dp_1(i)dp_{t-1}(n-i)\\ \frac{dp_t(n)}{(n-1)!}=\sum_{i=1}^n\frac{dp_1(i)}{(i-1)!}\frac{dp_{t-1}(n-i)}{(n-i)!}$$

那么

$$\hat{G}_t=\sum_{n\ge 0}dp_t(n)\frac{x^n}{n!}\\ \hat{F}=\sum_{n\ge 1}dp_1(n)\frac{x^n}{(n-1)!}$$

容易得到

$$n\hat{G}_t=\hat{F}\hat{G}_{t-1}+1$$

$dp_1(n)$就是$\ln G(n)$。

清华集训 2017 生成树计数

在一个 s 个点的图中，存在 s-n 条边，使图中形成了 n 个连通块，第 i 个连通块中有$a_i$个点。

现在我们需要再连接 n-1 条边，使得该图变成一棵树。对于一种连边方案，设原图中第$i$个连通块连出了$d_i$条边，那么这棵树$T$的价值为：

$$val(T)=\left( \prod_{i=1}^nd_i^m \right)\left( \sum_{i=1}^nd_i^m \right)$$

求出所有可能的生成树的价值之和，对$998244353$取模。

$n\le 3\times 10^4,m\le 30$。

转化为 n 个点的生成树 T：

$$\begin{aligned} &\left( \prod_{i=1}^nd_i^m \right)\left( \sum_{i=1}^nd_i^m \right)\left( \prod_{i=1}^na_i^{d_i} \right)\\ =&\sum_T\sum_{i=1}^na_i^{d_i} d_i^{2m}\prod_{j\ne i}(a_j^{d_j}d_j^{m})\\ =&\sum_{\sum k_i=n-2}\binom{n-2}{k_1,k_2,\cdots,k_n}\sum_{i=1}^na_i^{k_i+1}(k_i+1)^{2m}\prod_{j\ne i}\left(a_j^{k_j+1}(k_j+1)^{m}\right) \end{aligned}$$

交换

$$(n-2)!\sum_{i=1}^n\sum_{\sum k_i=n-2}\frac{1}{\prod k_i!}a_i^{k_i+1}(k_i+1)^{2m}\prod_{j\ne i}a_j^{k_j+1}(k_j+1)^{m}\\ (n-2)!\sum_{i=1}^n\sum_{\sum k_i=n-2}\frac{a_i^{k_i+1}(k_i+1)^{2m}}{k_i!}\prod_{j\ne i}\frac{a_j^{k_j+1}(k_j+1)^{m}}{k_j!}$$

EGF

$$B_i(x)=\sum_{k\ge 0}a_i^{k+1}(k+1)^{2m}\frac{x^k}{k!}\\ A_i(x)=\sum_{k\ge 0}a_i^{k+1}(k+1)^{m}\frac{x^k}{k!}$$

带回

$$[x^{n-2}](n-2)!\sum_{i=1}^n B_i(x)\prod _{i\ne j}A_j(x)$$

定义$T(x)$：

$$\begin{aligned} T(x)&=\int A_i(x)\text{d}x=\sum_{k\ge 1}a_i^kk^m\frac{x^k}{k!}\\ &=\sum_{k\ge 1}a_i^k\frac{x^k}{k!}\sum_{j=0}^mS(m,k)k^{\underline{j}}\\ &=\sum_{j=0}^mS(m,j)a_i^jx^je^{a_ix}\\ \end{aligned}$$

那么复合函数求导得到（sum 里是个复合函数）

$$\begin{aligned} A_i(x)&=\frac{\text{d}T(x)}{\text{d}x}=\sum_{j=0}^mS(m,j)a_i^jjx^{j-1}e^{a_ix}+\sum_{j=0}^mS(m,j)a_i^{j+1}x^je^{a_ix}\\ &=e^{a_ix}\sum_{j=0}^mS(m,j+1)(j+1)a_i^{j+1}+S(m,j)a_i^{j+1}\\ &=e^{a_ix}\sum_{j=0}^mS(m+1,j+1)a_i^{j+1}x^j \end{aligned}$$

复杂度$O(nm\log_2^2n)$。

Burnside 引理

ARC 62 F Painting Graphs with AtCoDeer

题意：给出无向图 G，对边染 K 种颜色之一。一个环上面的边旋转后得到的染色方案视为相同，求不同的染色方案数。

求出所有的点双（每个点双是独立的）：

1. 单独的边：方案数为 K。
2. 单环：$\frac{1}{n}\sum_{d=0}^{n-1}k^{\gcd(n,d)}$。
3. 复合环：可以交换两条边的颜色。只用统计不同颜色出现次数的方案数。插板$\binom{n+k-1}{k-1}$。

乘起来即可。