【泛学笔记】组合计数杂项

大概是听课听来的组合计数相关.jpg

广义二项式定理

$a\in \mathbb{R}$

泰勒展开证明。

抽屉原理一个比较有意思的表达

把 $kx+b$ 个物品放进 $x$ 个盒子里 $(0<b\leq k)$,必有 $1$ 个盒子里面至少有 $k+1$ 个物品。

卡特兰数

方格行走数。

瞎jb走,从$0,0$到$n,0$,共$2n$次决策,选$n$次向下。

减去走错了的,考虑我们第一次走到 $y=-1$ 这条直线上,关于这条直线把 $(n,0)$ 对称下来,然后就变成了从 $(0,0)$ 走到 $(n,-2)$ 的问题,即选择 $n-1$ 步向上,$n+1$ 步向下。

然后,我sd了,原因在于我思考了半天为什么减去的贡献不用 $\times 2$,因为这不对称,结果发现原来走到 $y=1$ 是合法的,艹,脑袋莫得了。

第一类斯特林数

有符号的第一类斯特林数记作$\rm \mathrm{S}_s$,无符号记作$\rm \mathrm{S}_u$。

圆排列方案数。

同时 $\rm \mathrm{S}_s$ 的生成函数是 $x^{\underline{n}}$,即固定 $n$ 不变时,$\rm \mathrm{S}_s$ 的 $m$ 在 $1\to \infty$ 时的生成函数是 $x$ 的 $n$ 次下降幂。

($n$ 固定下来之后的某一行)

第二类斯特林数:

贝尔数为第二类斯特林数之和,即把 $n$ 个数拆成 $k~(k\in \mathbb{N+})$ 集合的方案数之和。

ps:二斯都是不带标号的,似乎因为定义出来也没啥意义吧。

拆分数的非OGF做法

第二类斯特林数实际上是$\boldsymbol{n}$带标号(n个不同物品),$\boldsymbol{m}$不带标号

当$n,m$都无标号时,这个问题实际上就是拆分数问题,即$3=2+1$只代表一种情况,而如果有标号的话应该是三种情况($C_3^2$).

那么对于这个问题,考虑两种$dp$.

  • 1、令 $f_{i,j}$ 表示对于 $i$ 拆分成若干个不大于 $j$ 的数的方案数。则有转移:后面一项 $f_{i-j,j}$ 可以看成一个背包一样,后面的状态对前面的状态有天然的累加效应,所以只需要考虑丢到一个 $j$ 的情况;而前面一项则把我们转移从后一项的等于 $j$ 升级成为不大于 $j$ 。
  • 2、令 $g_{i,j}$ 表示对于 $i$ 拆分成 $j$ 个数的方案数。则有转移:前面一项表示新拆出一个 $1$ 来,还是背包的那种“累加”思想,所以只需要考虑拆出一个 $1$ 的情况;后面一项则表示不拆,而是把拆出的数全体都 $+1$,即本来的 $5=3+1+1$ 转移到 $8=4+2+2$ 。注意此处不会存在“部分拆出来的数加了但是剩下的没加”或者“加的不一样”,因为这两个状态都是可以归约到 $i$ 较小的 $g$ 上去所以不需要额外转移。

嗯,所以有时候状态的转移与设计存在“高阶状态对低阶状态有天然的累加效应”,换个不严谨的措辞就是+运算使得存在状态间的的相互归约。这是设计状态中需要考虑的一个新奇的东西。

ps:似乎某硬币xx的容斥题就用到了这个思想来着。。。实际上就是个背包吧qaq

LOJ 6268 分拆数

发现是 #6 的升级版。

考虑根号分治。先用 $f$ 求出来 $j\leq \sqrt n$ 的方案数,再魔改一下 $g$,让 $g$ 只转移那些 $\geq \sqrt n$ 的数字,具体就是第一维把 $\sqrt n$ 当作步长转移即可。

之后考虑合并这两个转移。发现最后转移完做一个累加,统计出两个多项式来,分别代表凑出体积 $i$ 的方案数。那么两个多项式的合并就是一个卷积的形式,就直接 $\rm NTT$ 做就完了。

连通图计数

定义连通图的 $\rm EGF$ 为 $F(x)$,任意图的 $\rm EGF$ 为 $G(x)$ 。

考虑

那么考虑一定有 $G(x)=e(F(x))$ ,即 $F(x)=\ln G(x)$ 。

这是因为任意图本身由任意个连通图构成,即考虑 $G$ 的另一种组成方式,从分成的连通块个数进行讨论。那么由 $n$ 个连通块构成的图,应该至少有 $F^n$ ,并且由于带标号且无序,所以 $F$ 应该用指数生成函数来刻画。

也就是从连通块的角度来考虑:

然后就可以肥宅快乐 $\exp$ 了。

大概类似于变换组合对象构造恒等式这种操作。

Best Theorem

一个有向图G,欧拉回路的数量是

其中 $t_1(G)$ 表示 $G$ 中以 $1$ 为根的生成树的数量。

杂题

A

给定一个 $n$ 个点 $m$ 条边的图,每条边有长度 $d_i$ 和价值 $v_i$。 随机选出一个长度和最小的生成树,求价值和的期望。

$n, m ≤ 50$

考虑如果长度都是 $1$(或者所有边长度均相同,本质是一样的),那么可以很方便地从每条边的贡献入手。大致就是考虑删掉一条边,用剩下的求一遍生成树计数,那么就可以算出这条边被选上的概率,这样就可以一条边一条边的计算贡献。复杂度 $mn^3$。

如果不是,那么考虑按照权值递增的顺序做如下过程:把当前最小的边拿出来,这样会是多个联通块。考虑在最后的生成树中,这样的边的权值一定会体现在其中,所以相当于每个联通块内选出一棵树,由于现在边权相等所以做法可以先用上一段里的方法。之后考虑把这个联通块缩成一个点,继续做下去,直到边满了为止。

似乎这样做不是很需要注意细节。因为本质上就是在重复一个贪心MST的过程。

B

给定一张 $n$ 个点,$m$ 条边的无向图,每条边有红绿蓝三种颜色,要求绿边数量不超过 $g$, 蓝边不超过 $b$ 的生成树数量,答案对 $10^9 + 7$ 取模

$n ≤ 40$

考虑给每条绿边一个权值变量 $x$, 每条蓝边一个权值变量 $y$,根据扩展 MT 定理,最终只需要对着 $xy$ 的次数找系数即可。

而问题在于如何求这样一个行列式。考虑带入 $n^2$ 对点值给 $x$ 和 $y$,最终使用这些点值进行二维插值,恢复出本来的多项式。复杂度似乎是 $O(n^5)+O(n^4\sim n^6)$ 。

二维插值怎么可能会的嘛,所以复杂度不重要,反正我也不会去写。

C

给定一个带权无向图,定义一棵生成树的权值是边权和的 $k$ 次方,求所有生成树的权值和,答案对 $10^9 + 7$ 取模。

$n, k ≤ 50$

一步转化,考虑一堆数的 $k$ 次方等价于从这堆数里选出 $k$ 个可重复的数字的积 (考虑顺序),再求和。

那么可以将每条边的边权重新定义一个多项式

表示一条边所代表的权值具体被选了若干次的权值。对新的权值使用 Matrix-tree, 得到一个 $nk$ 次的多项式,$x_k$ 的系数乘上 $k!$ 就是答案。