【推荐】拉反的简单组合解释
x义x
·
·
个人记录
这篇文章的目的是普及拉格朗日反演的证明。如果您觉得哪里有 gap 或者表述不清晰，请私信我或者在这篇博客下面留言。
问题.
证明下述的拉格朗日反演。
现有形式幂级数 f,g 满足 f=xg(f)，则有
\boxed{[x^n]h(f)=\dfrac 1n[x^{n-1}]h'g^n}
解答.
我们只需要证明
n[x^n]h(f)=[x^n](xh')g^n
首先考虑到条件 f=xg(f)，我们构造这样的树 \tau：
- 编号为 0\sim n，根为 0
- 一个节点 u 若度数为 d_u，则其权值为
\begin{cases}[x^d/d!]g&(u\neq 0)\\ [x^d/d!]h&(u=0)\end{cases}
（其中 [x^n/n!]f 这个记号可能不常用，它等于 n![x^n]f）
- 令 \tau 的权值 w(\tau) 为其所有节点的权值之积。
于是 LHS（left hand side，左式）便是所有 \tau 的权值之和。
接下来解释 RHS。考虑这样的有向图 g：
- 编号为 0\sim n，每个除 0 以外的点恰有一条出边，0 没有出边（从而 g 一定是一棵以 0 为根的内向树和若干内向基环树）
- 一个节点 u 若入度为 d_u，则其权值为
\begin{cases}[x^d/d!]g&(u\neq 0)\\ d[x^d/d!]h&(u=0)\end{cases}
- 令 g 的权值 w(g) 为其所有节点的权值之积。
我们来证明一个比拉格朗日反演更强的结论：考虑 0 的度数为 k，其余点中有 m_i 个度数为 i 的那些 \tau 和 g，我们来证明，\sum w(\tau)=\sum w(g)。显然对所有的 k,m 求和便得到拉格朗日反演定理。
显然 \tau,g 的权值和它们本身的细节无关，且总是有
w(g)=kw(\tau)
记满足上述条件的 \tau 的数量为 \#\tau，g 亦然，于是为了证明拉格朗日反演，我们只需要说明
\dfrac nk\#\tau=\#g
根据 Prüfer 序列，
\#\tau=\dfrac{(n-1)!}{(k-1)!1!^{m_1}2!^{m_2}....}{n\choose m_1,m_2,...}
对于 \#g，直接考虑每条边连向谁即可，
\#g=\dfrac{n!}{k!1!^{m_1}2!^{m_2}...}{n\choose m_1,m_2,...}
立即得证。
从而拉格朗日反演只是套了个皮的 Prüfer 序列……
\blacksquare
后记.
多元拉格朗日反演的证明事实上也与之非常类似，甚至于这篇论文直接称其为“Prüfer-like”的。不过它的确复杂得多。