其实就是把论文翻译了一遍(
0 目录
- 1 矩阵树定理的组合解释
- 2 多元拉格朗日反演
- 2.0 多元拉反的组合解释
- 2.0.1 基础定义
- 2.0.2 具体解释
- 2.1 内向树形式
- 2.2 多元拉反的双射证明
- 2.2.1 基础定义
- 2.2.2 函数图的子结构
- 2.2.3 树形子结构双射定理
- 2.2.4 结局
- 2.3 主子式扩展
- 2.4 主子式扩展的组合解释
- 2.4.1 右式的处理
- 2.4.2 左式的处理
- 3 参考资料
1 矩阵树定理的组合解释
考虑某矩阵
其中
可以看到其中的 sigma 枚举了所有并为
在基尔霍夫矩阵中,它的行为是这样的:
我们默认去掉的是第一行和第一列。这个东西可以这么解释:
- 首先,为每个
的点随机选一个父亲,这解释了度数的出现; - 这时显然会有环,那么我们把环给容斥掉即可,无环的情况就是生成树。这解释了系数
。
去掉第一行第一列正代表了选取一个根。这也解释了为什么如果不去掉第一行第一列,基尔霍夫矩阵的行列式为
2 多元拉格朗日反演
下面把
现有一列
那么我们有
多元拉格朗日反演.
其中:
2.0 多元拉反的组合解释
2.0.1 基础定义
定义我们研究的点集:
- 令
,说人话就是有 种颜色的点,第 种颜色的有 个。 - 记
,称这个新加的 节点的颜色为 。 - 记
为 。只是一个代表元素,用于下面的构造。
下面定义函数图。
- 函数图是一种有向图,每个点有且仅有一条出边,这个图对应一个函数
:边 意味着 。 - 记
是从 到 的函数图构成的集合,也就是说这个函数的定义域为 ,到达域为 。容易发现 中的函数是由一个包含 的内向树和一些内向基环树构成的。 - 而
是其中的以 为根的内向树(又出现了)的集合。
接下来定义权值。
对于某个
,其中的节点 的权值 定义如下:令 为颜色为 的,映射到 的节点数量,则定义
。
这时我们可以立即解释
正是我们最开始提到的方程组,即
引理 1.
2.0.2 具体解释
我们已经看到多元拉反的左式有直接的组合意义,下面我们来解释右式。
考虑
2.1 内向树形式
当然也可以暴力展开行列式。中间过程不表,类似之前对矩阵树定理的证明,只有一个观察是
多元拉格朗日反演(内向树形式).
其中 是完全图 的所有以 为根的生成内向树,而
这里的符号可能引起一些歧义,说明一下:
指的是 。但
指的是 。
我们给出对内向树形式的一个双射证明。
2.2 多元拉反的双射证明
2.2.1 基础定义
沿用之前的点集等定义。
2.2.2 函数图的子结构
接下来我们定义两种函数图的子结构。
对于某个
,它的路图 是一个 图,它如此构造:首先令已经处理的颜色序列为 。- 令
找出
中的单向路径 ,它从 延伸到第一个颜色为 或其颜色已被处理的节点 上有边 ,令离 最近且与 同色的节点为 (它当然可以为 自身)。- 令
为 的颜色,令 。令 为 到 的路径(含)。 - 在
中连边 。
- 令
这里给出一个例子。
记只保留
的 为 。一个
是 rlmax 的,如果 。
可见路图的性质是复杂的。我们下面给出它的一些有用的性质。
引理 2. 路图具有以下性质:
如果
是 rlmax 的,那么 。否则 。
皆是以 为根的内向树,且其最小叶子为 。
中没有颜色为 的节点。
证明不表,因为均可直接由构造过程得出。
- 对于某个
,它的色图 是一个 图。如果在 中存在 则在其色图中连边 。
这两种子结构的意义在于,我们即将通过它们建立一个从某类内向树到某类函数图的双射。(你可能会注意到内向树是函数图的一个子集,但是对无限集来说,某集合是另一集合的子集并不妨碍它们之间可以双射)
先进行一些准备工作:研究一些被称为保权值的变换:变换前后两个图的权值相等。
- 首先我们可以交换两个相同颜色节点
的父亲,称为 转换 (u,v),这显然是保权值的。 - 先选定颜色为
的两个节点 ,其中间有一条有向路径 自 到 。下面这个变换称为 c - 剥皮: - 从
倒回到 ,检查出那些颜色为 且比迄今为止遇到的所有颜色为 的节点标号都大的节点,称为 。构造新图 ,其中 就是 的 - 剥皮。
- 从
- 显然剥皮是保权值的。
现在我们终于可以给出下面这个定理。
2.2.3 树形子结构双射定理
定理 1.(树形子结构双射)
证明. 对于
- 剥下 ; :转换 ;
接下来我们只需要证明:最终得出的图
首先指出,第
于是,当
接下来我们展示上面的变换的可逆性。
首先,我们的确可以恢复
,只需要重复使用引理 2.2。通过
和引理 2.1,我们可以恢复 和 。显然
是可逆的。- 下面说明
也是可逆的。我们找到图中环上有 但没有 的那些基环树,环上面颜色为 中标号最大的元素就是原来的 ,逆也就显然了。
2.2.4 结局
接下来,我们只需要证明
引理 3.
证明. 如果不管
现在考虑
然后对每一个内向树
2.3 主子式扩展
还有一个奇妙的扩展,也一并介绍好了。
主子式多元拉格朗日反演.
其中 表示仅留下原矩阵的 中的行列的子矩阵(主子式)的行列式。 表示 的补。
接下来,我们给出一个对这个主子式扩展的组合解释。
2.4 主子式扩展的组合解释
直接沿用对普通多元拉反的组合解释。在引理 3 之后,我们已经得到
我们的目的是,对规定的
2.4.1 右式的处理
定理 2.
证明. 只需要对引理 3 运用矩阵树定理即可。还有别忘了
2.4.2 左式的处理
接下来,我们介绍 Gessel - Viennot cancellation(可以参见参考资料 [4],但不必要)。先对
- 对于
,找出 到 的路径,记 之前的最后一个点为 。记 到 的路径为 。 - 令
是 中离 最近的,颜色为 的节点。显然,它可能没有定义。
下面定义一种树集
- 对于
, 两两不交 - 对于
,记 的颜色为 , 恰好构成 的一个排列。
如果还满足下面的条件,则称其属于
- 对于
, 中不含颜色大于 的节点。这意味着 就是 本身。
我们认识到,
定理 3.
证明.
首先,我们有
下面我们来证明
这其实是一个容斥(也就是所说的 Gessel - Viennot cancellation)。考虑这样一个定义在
- 令
是使得 中存在一个节点颜色大于 的最大的 ; - 令
是 中最大的颜色。 - 对
施以转换 ,其结果便是 。
可见的是
综上,我们得到
现在只需要考虑对
对
综合左式和右式的处理即得到原定理。
3 参考资料
[1] A Multivariate Lagrange Inversion Formula for Asymptotic Calculations
[2] Multivariable Lagrange Inversion, Gessel-Viennot Cancellation, and the Matrix Tree Theorem
[3] A Bijetive Proof for the Arboresent Form of the Multivariable Lagrange Inversion Formula
[4] Determinants, Paths, and Plane Partitions
(↑ [5] 说的 cactus 其实指的是 constellation,不是 OI 里的仙人掌)
[6] 生成函数的一丶进展(WC2021 营员交流)