全是抄的某 xyx 的博客！
拉格朗日反演
考虑扩展拉格朗日反演：
对形式幂级数 F∘G=x,H，有 [xn]H∘F=1n[xn−1]H′(xG)n
这等价于对形式幂级数 f=xg(f),h 证明 n[xn]h(f)=[xn](xh′)gn
由于我们使用有标号对象建立双射，不妨将两边乘上 n!。
LHS
考虑 LHS 中的 n![xn]h(f)，注意到 f=xg(f) 显示出某种树的结构，而复合等价于在根处连接若干棵子树，考虑构造有根树 τ 满足：
- 以 0…n 编号，0 为根。
- 令结点 u 的儿子数为 du，则其权值为 {du![xdu]h,u=0du![xdu]g,u≠0
- 整棵树的权值 w(τ) 为所有结点的权值之积。
RHS
考虑 RHS 中的 ngn，此时似乎并没有特别的结构便于刻画，不过可以直接考虑 {0,1,…,n} 的一个 n 排列 α（等价于一张 n+1 点 n 边的有向图）：
- 令结点 u 的入度为 du，则其权值为 {du⋅du![xdu]h,u=0du![xdu]g,u≠0
- 整张图的权值 w(α) 为所有结点的权值之积。
进一步证明
考虑一个更强的结论：令 d0=k，ci=|{u∣du=i}|，此时的 ∑w(τ)=∑w(α)。对所有的 k 和 ci 求和便得证拉格朗日反演。
显然 kw(τ)=w(α)
记 #τ,#α 为满足条件的树和排列的个数，那么只需要考虑证明 nk#τ=#α
考虑 #τ，显然直接套用 Prufer 序列的结论即可： #τ=(nc1,c2,…)(n−1)!(k−1)!∏i!ci
考虑 #α，简单组合数学，考虑每条边从哪里连过来： #α=(nc1,c2,…)n!k!∏i!ci
证毕。
矩阵树定理
考虑一个矩阵 A 的行列式 detA=∑psgn(p)w(p)
考虑 p 的循环分解 p=∪{qi}，显然 detA=∑∪{qi}=p∏isgn(qi)w(qi)
考虑一个循环置换 q 的 sgn，显然 sgn(q)=(−1)|q|−1。而对于 w(q)≠0，只有两种情况：单点或环。前者的权值即是其度数，后者则是 (−1)|q|。
从而删去第一行第一列的 n−1 阶主子式即是 ∑∪{qi}=[2,n]∏i{degq,|q|=1−1,q is a cycle in G
考虑这个东西，它等价于在每个点相邻的点中选定一个父亲，然后容斥掉环。
不过这里假定了 G 是简单无向图，事实上其他情况也不难类似地证明。
多元拉格朗日反演
咕咕咕。
停课的时候再补。