本地源文件：docs/math__poly__lagrange-inversion.md

Lagrange 反演

形式 Laurent 级数

我们已经知道形式幂级数环 ℂ[[𝑥]]C[[x]] 了，定义形式 Laurent 级数环：

ℂ((𝑥)):={∑𝑘≥𝑁𝑎𝑘𝑥𝑘:𝑁∈ℤ,𝑎𝑘∈ℂ}C((x)):={∑k≥Nakxk:N∈Z,ak∈C}

我们可以仿照形式幂级数的乘法逆元定义来定义 ℂ((𝑥))C((x)) 上元素的乘法逆元：

若对于 𝑓 :=∑𝑘≥𝑁𝑓𝑘𝑥𝑘f:=∑k≥Nfkxk 且 𝑓𝑁 ≠0fN≠0 存在 𝑔 =∑𝑘≥−𝑁𝑔𝑘𝑥𝑘g=∑k≥−Ngkxk 满足 𝑓𝑔 =1fg=1 那么

𝑔𝑘:={𝑓−1𝑁, if 𝑘=−𝑁,−𝑓−1𝑁∑𝑖>𝑁𝑓𝑖𝑔𝑘−𝑖, otherwisegk:={fN−1, if k=−N,−fN−1∑i>Nfigk−i, otherwise

与形式幂级数类似的，我们也对非零的 𝑓(𝑥) =∑𝑘≥𝑁𝑓𝑘𝑥𝑘f(x)=∑k≥Nfkxk 定义：

ord⁡𝑓:=min{𝑘:𝑓𝑘≠0}ord⁡f:=min{k:fk≠0}

显然对于 𝑔 ≠0g≠0 有

ord⁡(𝑓𝑔)=ord⁡(𝑓)+ord⁡(𝑔)ord⁡(fg)=ord⁡(f)+ord⁡(g)

形式留数

形式留数是形式 Laurent 级数中 𝑥−1x−1 项的系数．记 res⁡𝑓 :=[𝑥−1]𝑓res⁡f:=[x−1]f．

引理：对于任何形式 Laurent 级数 𝑓f 有 res⁡𝑓′ =0res⁡f′=0．

证明：考虑形式导数的定义 (𝑥𝑘)′ =𝑘𝑥𝑘−1(xk)′=kxk−1．

引理：对于任何形式 Laurent 级数 𝑓,𝑔f,g 有 res⁡(𝑓′𝑔) = −res⁡(𝑓𝑔′)res⁡(f′g)=−res⁡(fg′)．

证明：考虑乘法法则 (𝑓𝑔)′ =𝑓′𝑔 +𝑓𝑔′(fg)′=f′g+fg′ 所以 0 =res⁡((𝑓𝑔)′) =res⁡(𝑓′𝑔) +res⁡(𝑓𝑔′)0=res⁡((fg)′)=res⁡(f′g)+res⁡(fg′)．

引理：对于形式 Laurent 级数 𝑓(𝑥) ≠0f(x)≠0 有 res⁡(𝑓′/𝑓) =ord⁡𝑓res⁡(f′/f)=ord⁡f．

证明：设 ord⁡𝑓 =𝑘ord⁡f=k 那么

res⁡(𝑓′𝑓)=res⁡(𝑘𝑓𝑘𝑥𝑘−1+⋯𝑓𝑘𝑥𝑘+𝑓𝑘+1𝑥𝑘+1+⋯)=res⁡(𝑘𝑓𝑘𝑥−1+⋯𝑓𝑘+𝑓𝑘+1𝑥+⋯)=𝑘res⁡(f′f)=res⁡(kfkxk−1+⋯fkxk+fk+1xk+1+⋯)=res⁡(kfkx−1+⋯fk+fk+1x+⋯)=k

引理：对于形式 Laurent 级数 𝑓f 和形式幂级数 𝑔 ≠0g≠0 有 res⁡(𝑓)ord⁡(𝑔) =res⁡(𝑓(𝑔)𝑔′)res⁡(f)ord⁡(g)=res⁡(f(g)g′)．

证明：考虑线性性，我们只需证明 𝑓 =𝑥𝑘f=xk 其中 𝑘 ∈ℤk∈Z 的情况即可，若 𝑘 ≠ −1k≠−1 那么

res⁡𝑥𝑘=0res⁡(𝑔𝑘𝑔′)=res⁡(1𝑘+1(𝑔𝑘+1)′)=1𝑘+1res⁡((𝑔𝑘+1)′)=0res⁡xk=0res⁡(gkg′)=res⁡(1k+1(gk+1)′)=1k+1res⁡((gk+1)′)=0

若 𝑘 = −1k=−1 那么

res⁡𝑓=res⁡(𝑥−1)=1res⁡(𝑓(𝑔)𝑔′)=res⁡(𝑔′/𝑔)=ord⁡(𝑔)=res⁡(𝑓)ord⁡(𝑔)res⁡f=res⁡(x−1)=1res⁡(f(g)g′)=res⁡(g′/g)=ord⁡(g)=res⁡(f)ord⁡(g)

复合逆

记 𝐴(𝑥) ∘𝐵(𝑥) :=𝐴(𝐵(𝑥))A(x)∘B(x):=A(B(x))．

命题：𝑓(𝑥) :=∑𝑘≥1𝑓𝑘𝑥𝑘f(x):=∑k≥1fkxk 存在复合逆 𝑓⟨−1⟩(𝑥)f⟨−1⟩(x) 当且仅当 𝑓(0) =0 ≠𝑓′(0)f(0)=0≠f′(0)，此时 𝑓⟨−1⟩(𝑥)f⟨−1⟩(x) 是唯一的．进一步说：若 𝑔(𝑥) =∑𝑘≥1𝑔𝑘𝑥𝑘g(x)=∑k≥1gkxk 满足 𝑓(𝑔(𝑥)) =𝑥f(g(x))=x 或 𝑔(𝑓(𝑥)) =𝑥g(f(x))=x 那么 𝑔(𝑥) =𝑓⟨−1⟩(𝑥)g(x)=f⟨−1⟩(x)．

证明：考虑

𝑔(𝑓(𝑥))=𝑔1(𝑓1𝑥+𝑓2𝑥2+𝑓3𝑥3+⋯)+𝑔2(𝑓1𝑥+𝑓2𝑥2+⋯)2+𝑔3(𝑓1𝑥+⋯)3+⋯=𝑔1𝑓1𝑥+(𝑔1𝑓2+𝑔2𝑓21)𝑥2+(𝑔1𝑓3+2𝑔2𝑓1𝑓2+𝑔3𝑓31)𝑥3+⋯g(f(x))=g1(f1x+f2x2+f3x3+⋯)+g2(f1x+f2x2+⋯)2+g3(f1x+⋯)3+⋯=g1f1x+(g1f2+g2f12)x2+(g1f3+2g2f1f2+g3f13)x3+⋯

因为 𝑔(𝑓(𝑥)) =𝑥g(f(x))=x 所以有下面的方程组

⎧{ { {⎨{ { {⎩𝑔1𝑓1=1𝑔1𝑓2+𝑔2𝑓21=0𝑔1𝑓3+2𝑔2𝑓1𝑓2+𝑔3𝑓31=0⋮{g1f1=1g1f2+g2f12=0g1f3+2g2f1f2+g3f13=0⋮

我们只能在 𝑓1 ≠0f1≠0 时才能解出第一个等式，然后依次可以解出 𝑔2,…g2,…．

特别的，考虑 𝑓(ℎ(𝑥)) =𝑥f(h(x))=x 那么 𝑔(𝑓(ℎ(𝑥))) =𝑔(𝑥)g(f(h(x)))=g(x)，进而 𝑔(𝑥) =𝑔 ∘𝑓 ∘ℎ(𝑥) =𝑥 ∘ℎ(𝑥) =ℎ(𝑥)g(x)=g∘f∘h(x)=x∘h(x)=h(x)．

Lagrange 反演公式

令 𝑓(𝑥),𝑔(𝑥) ∈ℂ[[𝑥]]f(x),g(x)∈C[[x]] 满足 𝑓(𝑔(𝑥)) =𝑔(𝑓(𝑥)) =𝑥f(g(x))=g(f(x))=x．取 Φ(𝑥) ∈ℂ[[𝑥]]Φ(x)∈C[[x]]（或 Φ(𝑥) ∈ℂ((𝑥))Φ(x)∈C((x))），那么

[𝑥𝑛]Φ(𝑓(𝑥))=[𝑥𝑛−1]Φ(𝑥)𝑔′(𝑥)𝑔(𝑥)(𝑥𝑔(𝑥))𝑛=[𝑥−1]Φ(𝑥)𝑔′(𝑥)𝑔(𝑥)𝑛+1[xn]Φ(f(x))=[xn−1]Φ(x)g′(x)g(x)(xg(x))n=[x−1]Φ(x)g′(x)g(x)n+1

证明：

[𝑥𝑛]Φ(𝑓(𝑥))=res⁡(Φ(𝑓(𝑥))𝑥𝑛+1)=res⁡(Φ(𝑓(𝑔(𝑥)))𝑔′(𝑥)𝑔(𝑥)𝑛+1)⋅(ord⁡(𝑔(𝑥)))−1=res⁡(Φ(𝑥)𝑔′(𝑥)𝑔(𝑥)𝑛+1)[xn]Φ(f(x))=res⁡(Φ(f(x))xn+1)=res⁡(Φ(f(g(x)))g′(x)g(x)n+1)⋅(ord⁡(g(x)))−1=res⁡(Φ(x)g′(x)g(x)n+1)

一些读者可能会更加熟悉下面的版本：对于 𝑘 ∈ℤ≥0,𝑛 ∈ℤ>0k∈Z≥0,n∈Z>0 有

[𝑥𝑛]𝑓(𝑥)𝑘=𝑘𝑛𝑥𝑛−𝑘)𝑛[xn]f(x)k=knxn−k)n

或者

[𝑥𝑛]Φ(𝑓(𝑥))=1𝑛[𝑥𝑛−1]Φ′(𝑥)(𝑥𝑔(𝑥))𝑛=1𝑛[𝑥−1]Φ′(𝑥)𝑔(𝑥)𝑛[xn]Φ(f(x))=1n[xn−1]Φ′(x)(xg(x))n=1n[x−1]Φ′(x)g(x)n

发现

res⁡(Φ′(𝑥)𝑔(𝑥)𝑛−𝑛Φ(𝑥)𝑔′(𝑥)𝑔(𝑥)𝑛+1)=res⁡((Φ(𝑥)𝑔(𝑥)𝑛)′)=0res⁡(Φ′(x)g(x)n−nΦ(x)g′(x)g(x)n+1)=res⁡((Φ(x)g(x)n)′)=0

可以通过我们已经证明的部分导出．

参考文献

Richard P. Stanley and Sergey P. Fomin. Enumerative Combinatorics Volume 2 (Edition 1).
Ira M. Gessel. Lagrange Inversion.

本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Tiphereth-A, hly1204 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用