全是抄的某 xyx 的博客！

拉格朗日反演

考虑扩展拉格朗日反演：
对形式幂级数 \(F \circ G = x,H\)，有 \[ [x^n] H\circ F = \frac1n [x^{n-1}] H' \left(\frac xG\right)^n \]

这等价于对形式幂级数 \(f = xg(f),h\) 证明 \[ n [x^n] h(f) = [x^n] (xh')g^n \]

由于我们使用有标号对象建立双射，不妨将两边乘上 \(n!\)。

LHS

考虑 LHS 中的 \(n! [x^n] h(f)\)，注意到 \(f = xg(f)\) 显示出某种树的结构，而复合等价于在根处连接若干棵子树，考虑构造有根树 \(\tau\) 满足：

以 \(0\dots n\) 编号，\(0\) 为根。
令结点 \(u\) 的儿子数为 \(d_u\)，则其权值为 \[ \begin{cases} d_u! [x^{d_u}] h, & u=0 \\ d_u! [x^{d_u}] g, & u\ne0 \end{cases} \]
整棵树的权值 \(w(\tau)\) 为所有结点的权值之积。

考虑 RHS 中的 \(n! [x^n] (xh') g^n\)，此时似乎并没有特别的结构便于刻画，不过可以直接考虑 \(\{0,1,\dots,n\}\) 的一个 \(n\) 排列 \(\alpha\)（等价于一张 \(n+1\) 点 \(n\) 边的有向图）：

令结点 \(u\) 的入度为 \(d_u\)，则其权值为 \[ \begin{cases} d_u \cdot d_u! [x^{d_u}] h, & u=0 \\ d_u! [x^{d_u}] g, & u\ne0 \end{cases} \]
整张图的权值 \(w(\alpha)\) 为所有结点的权值之积。

考虑一个更强的结论：令 \(d_0=k\)，\(c_i = |\{u \mid d_u = i\}|\)，此时的 \(\sum w(\tau) = \sum w(\alpha)\)。对所有的 \(k\) 和 \(c_i\) 求和便得证拉格朗日反演。

显然 \[ k w(\tau) = w(\alpha) \]

记 \(\# \tau,\# \alpha\) 为满足条件的树和排列的个数，那么只需要考虑证明 \[ \frac nk \# \tau = \# \alpha \]

考虑 \(\# \tau\)，显然直接套用 Prufer 序列的结论即可： \[ \# \tau = \binom n{c_1,c_2,\dots} \frac{(n-1)!}{(k-1)!\prod i!^{c_i}} \]

考虑 \(\# \alpha\)，简单组合数学，考虑每条边从哪里连过来： \[ \# \alpha = \binom n{c_1,c_2,\dots} \frac{n!}{k!\prod i!^{c_i}} \]

证毕。

考虑一个矩阵 \(A\) 的行列式 \[ \def\sgn{ {\rm sgn} } \det A = \sum_p \sgn(p) w(p) \]

考虑 \(p\) 的循环分解 \(p = \cup \{q_i\}\)，显然 \[ \det A = \sum_{\cup\{q_i\} = p} \prod_i \sgn(q_i) w(q_i) \]

考虑一个循环置换 \(q\) 的 \(\sgn\)，显然 \(\sgn(q) = (-1)^{|q|-1}\)。而对于 \(w(q) \ne 0\)，只有两种情况：单点或环。前者的权值即是其度数，后者则是 \((-1)^{|q|}\)。

从而删去第一行第一列的 \(n-1\) 阶主子式即是 \[ \sum_{\cup\{q_i\} = [2,n]} \prod_i \begin{cases} \deg_q, & |q|=1 \\ -1, & q \text{ is a cycle in } G \end{cases} \]

考虑这个东西，它等价于在每个点相邻的点中选定一个父亲，然后容斥掉环。

不过这里假定了 \(G\) 是简单无向图，事实上其他情况也不难类似地证明。

咕咕咕。
停课的时候再补。