简略版的 LGV 和矩阵树证明

· · 算法·理论

前言

虽然说这个可以不用证，但是我觉得证明一下可以对一些高级应用有更深刻的理解，所以还是有一些必要的。我是一个蒟蒻，所以公式当然可能会有错误，并且借鉴了一些人的文章，请见谅。

让我们来 recollecter 一下行列式定义

\begin{aligned}\sum_p (-1)^{sgn(p)}\prod{a_i,_{p_i}}\end{aligned}

其中 p 是一个排列。sgn 指逆序对数量。这里可能和一般的定义有些不同。

LGV 部分

首先二元的 LGV 就是另两个终点交换一下，这样的话，两条路径就一定经过，可以正好容斥掉。对于多元的情况，可以试作对每一个 \prod a_i,_{p_i} 赋一个容斥系数。那么我们发现，一个逆序对相当于钦定这个这两条路线一定要相交对吧。那么我们考虑每个二元对，如果是顺序对，相当于不钦定，如果是逆序对，相当于钦定必须相交，那么把所有的二元队展开成一个序列，相当于在这个序列上容斥每个出所有位置都合法的情况。

一个可能难以理解的地方是，清定的了一些位置作为逆序对，可能对其他位置也会保证这些位置一定相交，那这样这个东西会不会错掉。其实是不会的，因为可以把 \frac{n(n-1)}{2} 个 01 状态视做一个个类。那么其实一个类要是不合法的话，答案就是零，这样的话，容斥出来理解一下仍然不会错。这里不要理解为对方案容斥，我觉得理解成对这些 01 状态容斥正确性会显然一些。

矩阵树部分

矩阵树。这个就复杂一点。先考虑无根树。那么假定第一个点为根，考虑一种乱搞：对，除了第一个点之外的每个点随便选一个父亲，并计算出这条连边的方案数乘在一起。那么显然可能出现环对吧。所以要对环容斥，钦定 x 个环，赋一个 (-1)^x 的系数即可。

另一个很重要的观察是，考虑一个排列将 i 和 p_i 连边，那么一定会形成一堆环。我们考虑用这个东西来钦定环。然后发现，交换 p 的两个元素后，逆序队奇偶性一定发生变化，因为在这两个数中间或者左右或者上下的都不会受到影响，然后他们两个交换之后，要么是零个变成一个，要么是一个变成零个，所以奇偶性一定会变化。然后交换两个数之后环的奇偶性也一定会发生变化。因为如果他们在同一个环内，那一定会把这个环裂开，如果在不同环内一定会把两个环给合并起来。那么使用数学归纳法发现，那个容斥系数就是 (-1)^{sgn(p)+n}。

于是，相当于枚举一个集合，然后给他赋一个上面的权值再加上除了这个集合里面的点的度数的乘积，因为不在这个集合里的点相当于可以任选父亲，那么贡献就一定是他的度数。在枚举排列的时候，假设这个排列在不包含在集合里的那些位置强令 i=p_i。设 f(p) 表示排列的 p_i=i 的集合。注意这里要扣去根。所以柿子是：

\begin{aligned}\sum_{S}\prod_{i\in{S}}d_i\sum_{f(p)\supseteq{S}}(-1)^{sgn(p)}\prod_{i\notin{S}}{-a_i,_{p_i}}\\=\sum_{p}(-1)^{sgn(p)}\sum_{S\subseteq{f(p)}}\prod_{i\in{S}}d_i\prod_{i\notin{S}}{-a_i,_{p_i}}\\=\sum_{p}(-1)^{sgn(p)}\prod_i{([i=p_i]d_i-a_i,_{p_i})}\end{aligned}

第二步就是交换一下求和次序，第三步是使用多项式乘法的意义。于是就愉快的做完了。