Formal Laurent series
We already know the ring of formal power series C [ [ x ] ] \mathbb{C}\lbrack\lbrack x\rbrack\rbrack C [[ x ]]
C ( ( x ) ) : = { ∑ k ≥ N a k x k : N ∈ Z , a k ∈ C } \mathbb{C}\left(\left(x\right)\right):=\left\lbrace \sum_{k\geq N}a_kx^k : N\in\mathbb{Z},a_k\in \mathbb{C}\right\rbrace C ( ( x ) ) := { k ≥ N ∑ a k x k : N ∈ Z , a k ∈ C } We can define multiplicative inverses of elements of C ( ( x ) ) \mathbb{C}\left(\left(x\right)\right) C ( ( x ) )
If f : = ∑ k ≥ N f k x k f:=\sum_{k\geq N}f_kx^k f := ∑ k ≥ N f k x k f N ≠ 0 f_N\neq 0 f N = 0 g = ∑ k ≥ − N g k x k g=\sum_{k\geq -N}g_kx^k g = ∑ k ≥ − N g k x k f g = 1 fg=1 f g = 1
g k : = { f N − 1 , if k = − N , − f N − 1 ∑ i > N f i g k − i , otherwise g_k:=
\begin{cases}
f_N^{-1}, &\text{ if }k=-N\text{,} \\
-f_N^{-1}\sum_{i> N}f_ig_{k-i}, &\text{ otherwise}
\end{cases} g k := { f N − 1 , − f N − 1 ∑ i > N f i g k − i , if k = − N , otherwise As with formal power series, for a nonzero f ( x ) = ∑ k ≥ N f k x k f(x)=\sum_{k\geq N}f_kx^k f ( x ) = ∑ k ≥ N f k x k
ord f : = min { k : f k ≠ 0 } \operatorname{ord} f:=\min\lbrace k:f_k\neq 0\rbrace ord f := min { k : f k = 0 } Clearly, for g ≠ 0 g\neq 0 g = 0
ord ( f g ) = ord ( f ) + ord ( g ) \operatorname{ord} (fg)=\operatorname{ord}(f)+\operatorname{ord}(g) ord ( f g ) = ord ( f ) + ord ( g ) Formal residues
The formal residue is the coefficient of x − 1 x^{-1} x − 1 res f : = [ x − 1 ] f \operatorname{res} f:=\lbrack x^{-1}\rbrack f res f := [ x − 1 ] f
Lemma : For any formal Laurent series f f f res f ′ = 0 \operatorname{res} f'=0 res f ′ = 0
Proof : This follows from the definition of the formal derivative, ( x k ) ′ = k x k − 1 \left(x^k\right)'=kx^{k-1} ( x k ) ′ = k x k − 1
Lemma : For any formal Laurent series f , g f,g f , g res ( f ′ g ) = − res ( f g ′ ) \operatorname{res}(f'g)=-\operatorname{res}(fg') res ( f ′ g ) = − res ( f g ′ )
Proof : By the product rule ( f g ) ′ = f ′ g + f g ′ (fg)'=f'g+fg' ( f g ) ′ = f ′ g + f g ′ 0 = res ( ( f g ) ′ ) = res ( f ′ g ) + res ( f g ′ ) 0=\operatorname{res}((fg)')=\operatorname{res}(f'g)+\operatorname{res}(fg') 0 = res (( f g ) ′ ) = res ( f ′ g ) + res ( f g ′ )
Lemma : For a nonzero formal Laurent series f ( x ) ≠ 0 f(x)\neq 0 f ( x ) = 0 res ( f ′ / f ) = ord f \operatorname{res}(f'/f)=\operatorname{ord}f res ( f ′ / f ) = ord f
Proof : Let ord f = k \operatorname{ord}f=k ord f = k
res ( f ′ f ) = res ( k f k x k − 1 + ⋯ f k x k + f k + 1 x k + 1 + ⋯ ) = res ( k f k x − 1 + ⋯ f k + f k + 1 x + ⋯ ) = k \begin{aligned}
\operatorname{res}\left(\frac{f'}{f}\right)&=\operatorname{res}\left(\frac{kf_kx^{k-1}+\cdots}{f_kx^k+f_{k+1}x^{k+1}+\cdots}\right) \\
&=\operatorname{res}\left(\frac{kf_kx^{-1}+\cdots}{f_k+f_{k+1}x+\cdots}\right) \\
&=k
\end{aligned} res ( f f ′ ) = res ( f k x k + f k + 1 x k + 1 + ⋯ k f k x k − 1 + ⋯ ) = res ( f k + f k + 1 x + ⋯ k f k x − 1 + ⋯ ) = k Lemma : For a formal Laurent series f f f g ≠ 0 g\neq 0 g = 0 res ( f ) ord ( g ) = res ( f ( g ) g ′ ) \operatorname{res}(f)\operatorname{ord}(g)=\operatorname{res}(f(g)g') res ( f ) ord ( g ) = res ( f ( g ) g ′ )
Proof : By linearity, it is enough to prove the case f = x k f=x^k f = x k k ∈ Z k\in\mathbb{Z} k ∈ Z k ≠ − 1 k\neq -1 k = − 1
res x k = 0 res ( g k g ′ ) = res ( 1 k + 1 ( g k + 1 ) ′ ) = 1 k + 1 res ( ( g k + 1 ) ′ ) = 0 \begin{aligned}
\operatorname{res}x^k&=0 \\
\operatorname{res}(g^kg')&=\operatorname{res}\left(\frac{1}{k+1}\left(g^{k+1}\right)'\right) \\
&=\frac{1}{k+1}\operatorname{res}\left(\left(g^{k+1}\right)'\right) \\
&=0
\end{aligned} res x k res ( g k g ′ ) = 0 = res ( k + 1 1 ( g k + 1 ) ′ ) = k + 1 1 res ( ( g k + 1 ) ′ ) = 0 If k = − 1 k=-1 k = − 1
res f = res ( x − 1 ) = 1 res ( f ( g ) g ′ ) = res ( g ′ / g ) = ord ( g ) = res ( f ) ord ( g ) \begin{aligned}
\operatorname{res}f&=\operatorname{res}\left(x^{-1}\right)=1 \\
\operatorname{res}(f(g)g')&=\operatorname{res}(g'/g) \\
&=\operatorname{ord}(g) \\
&=\operatorname{res}(f)\operatorname{ord}(g)
\end{aligned} res f res ( f ( g ) g ′ ) = res ( x − 1 ) = 1 = res ( g ′ / g ) = ord ( g ) = res ( f ) ord ( g ) Compositional inverse
Write A ( x ) ∘ B ( x ) : = A ( B ( x ) ) A(x)\circ B(x):=A(B(x)) A ( x ) ∘ B ( x ) := A ( B ( x ))
Proposition : f ( x ) : = ∑ k ≥ 1 f k x k f(x):=\sum_{k\geq 1}f_kx^k f ( x ) := ∑ k ≥ 1 f k x k f ⟨ − 1 ⟩ ( x ) f^{\langle -1\rangle}(x) f ⟨ − 1 ⟩ ( x ) f ( 0 ) = 0 ≠ f ′ ( 0 ) f(0)=0\neq f'(0) f ( 0 ) = 0 = f ′ ( 0 ) f ⟨ − 1 ⟩ ( x ) f^{\langle -1\rangle}(x) f ⟨ − 1 ⟩ ( x ) g ( x ) = ∑ k ≥ 1 g k x k g(x)=\sum_{k\geq 1}g_kx^k g ( x ) = ∑ k ≥ 1 g k x k f ( g ( x ) ) = x f(g(x))=x f ( g ( x )) = x g ( f ( x ) ) = x g(f(x))=x g ( f ( x )) = x g ( x ) = f ⟨ − 1 ⟩ ( x ) g(x)=f^{\langle -1\rangle}(x) g ( x ) = f ⟨ − 1 ⟩ ( x )
Proof : Consider
g ( f ( x ) ) = g 1 ( f 1 x + f 2 x 2 + f 3 x 3 + ⋯ ) + g 2 ( f 1 x + f 2 x 2 + ⋯ ) 2 + g 3 ( f 1 x + ⋯ ) 3 + ⋯ = g 1 f 1 x + ( g 1 f 2 + g 2 f 1 2 ) x 2 + ( g 1 f 3 + 2 g 2 f 1 f 2 + g 3 f 1 3 ) x 3 + ⋯ \begin{aligned}
g(f(x))&=g_1(f_1x+f_2x^2+f_3x^3+\cdots ) \\
&+g_2(f_1x+f_2x^2+\cdots )^2 \\
&+g_3(f_1x+\cdots )^3 \\
&+\cdots \\
&=g_1f_1x+(g_1f_2+g_2f_1^2)x^2+(g_1f_3+2g_2f_1f_2+g_3f_1^3)x^3+\cdots
\end{aligned} g ( f ( x )) = g 1 ( f 1 x + f 2 x 2 + f 3 x 3 + ⋯ ) + g 2 ( f 1 x + f 2 x 2 + ⋯ ) 2 + g 3 ( f 1 x + ⋯ ) 3 + ⋯ = g 1 f 1 x + ( g 1 f 2 + g 2 f 1 2 ) x 2 + ( g 1 f 3 + 2 g 2 f 1 f 2 + g 3 f 1 3 ) x 3 + ⋯ Since g ( f ( x ) ) = x g(f(x))=x g ( f ( x )) = x
{ g 1 f 1 = 1 g 1 f 2 + g 2 f 1 2 = 0 g 1 f 3 + 2 g 2 f 1 f 2 + g 3 f 1 3 = 0 ⋮ \begin{cases}
g_1f_1&=1 \\
g_1f_2+g_2f_1^2&=0 \\
g_1f_3+2g_2f_1f_2+g_3f_1^3&=0 \\
\vdots
\end{cases} ⎩ ⎨ ⎧ g 1 f 1 g 1 f 2 + g 2 f 1 2 g 1 f 3 + 2 g 2 f 1 f 2 + g 3 f 1 3 ⋮ = 1 = 0 = 0 We can solve the first equation only when f 1 ≠ 0 f_1\neq 0 f 1 = 0 g 2 , … g_2,\dots g 2 , …
In particular, if f ( h ( x ) ) = x f(h(x))=x f ( h ( x )) = x g ( f ( h ( x ) ) ) = g ( x ) g(f(h(x)))=g(x) g ( f ( h ( x ))) = g ( x ) g ( x ) = g ∘ f ∘ h ( x ) = x ∘ h ( x ) = h ( x ) g(x)=g\circ f\circ h(x)=x\circ h(x)=h(x) g ( x ) = g ∘ f ∘ h ( x ) = x ∘ h ( x ) = h ( x )
Lagrange inversion formula
Let f ( x ) , g ( x ) ∈ C [ [ x ] ] f(x),g(x)\in\mathbb{C}\lbrack\lbrack x\rbrack\rbrack f ( x ) , g ( x ) ∈ C [[ x ]] f ( g ( x ) ) = g ( f ( x ) ) = x f(g(x))=g(f(x))=x f ( g ( x )) = g ( f ( x )) = x Φ ( x ) ∈ C [ [ x ] ] \Phi(x)\in\mathbb{C}\lbrack\lbrack x\rbrack\rbrack Φ ( x ) ∈ C [[ x ]] Φ ( x ) ∈ C ( ( x ) ) \Phi(x)\in\mathbb{C}\left(\left(x\right)\right) Φ ( x ) ∈ C ( ( x ) )
[ x n ] Φ ( f ( x ) ) = [ x n − 1 ] Φ ( x ) g ′ ( x ) g ( x ) ( x g ( x ) ) n = [ x − 1 ] Φ ( x ) g ′ ( x ) g ( x ) n + 1 \begin{aligned}
\lbrack x^n\rbrack\Phi(f(x))&=\lbrack x^{n-1}\rbrack\Phi(x)\frac{g'(x)}{g(x)}\left(\frac{x}{g(x)}\right)^n \\
&=\lbrack x^{-1}\rbrack\frac{\Phi(x)g'(x)}{g(x)^{n+1}}
\end{aligned} [ x n ] Φ ( f ( x )) = [ x n − 1 ] Φ ( x ) g ( x ) g ′ ( x ) ( g ( x ) x ) n = [ x − 1 ] g ( x ) n + 1 Φ ( x ) g ′ ( x ) Proof :
[ x n ] Φ ( f ( x ) ) = res ( Φ ( f ( x ) ) x n + 1 ) = res ( Φ ( f ( g ( x ) ) ) g ′ ( x ) g ( x ) n + 1 ) ⋅ ( ord ( g ( x ) ) ) − 1 = res ( Φ ( x ) g ′ ( x ) g ( x ) n + 1 ) \begin{aligned}
\lbrack x^n\rbrack\Phi(f(x))&=\operatorname{res}\left(\frac{\Phi(f(x))}{x^{n+1}}\right) \\
&=\operatorname{res}\left(\frac{\Phi(f(g(x)))g'(x)}{g(x)^{n+1}}\right)\cdot \left(\operatorname{ord}(g(x))\right)^{-1} \\
&=\operatorname{res}\left(\frac{\Phi(x)g'(x)}{g(x)^{n+1}}\right)
\end{aligned} [ x n ] Φ ( f ( x )) = res ( x n + 1 Φ ( f ( x )) ) = res ( g ( x ) n + 1 Φ ( f ( g ( x ))) g ′ ( x ) ) ⋅ ( ord ( g ( x )) ) − 1 = res ( g ( x ) n + 1 Φ ( x ) g ′ ( x ) ) Some readers may be more familiar with the following version: for k ∈ Z ≥ 0 , n ∈ Z > 0 k\in\mathbb{Z}_{\geq 0},n\in\mathbb{Z}_{>0} k ∈ Z ≥ 0 , n ∈ Z > 0
[ x n ] f ( x ) k = k n [ x n − k ] ( x g ( x ) ) n \lbrack x^n\rbrack f(x)^k=\frac{k}{n}\lbrack x^{n-k}\rbrack\left(\frac{x}{g(x)}\right)^n [ x n ] f ( x ) k = n k [ x n − k ] ( g ( x ) x ) n or
[ x n ] Φ ( f ( x ) ) = 1 n [ x n − 1 ] Φ ′ ( x ) ( x g ( x ) ) n = 1 n [ x − 1 ] Φ ′ ( x ) g ( x ) n \begin{aligned}
\lbrack x^n\rbrack \Phi(f(x))&=\frac{1}{n}\lbrack x^{n-1}\rbrack \Phi'(x)\left(\frac{x}{g(x)}\right)^n \\
&=\frac{1}{n}\lbrack x^{-1}\rbrack\frac{\Phi'(x)}{g(x)^n}
\end{aligned} [ x n ] Φ ( f ( x )) = n 1 [ x n − 1 ] Φ ′ ( x ) ( g ( x ) x ) n = n 1 [ x − 1 ] g ( x ) n Φ ′ ( x ) Observe that
res ( Φ ′ ( x ) g ( x ) n − n Φ ( x ) g ′ ( x ) g ( x ) n + 1 ) = res ( ( Φ ( x ) g ( x ) n ) ′ ) = 0 \begin{aligned}
\operatorname{res}\left(\frac{\Phi'(x)}{g(x)^n}-n\frac{\Phi(x)g'(x)}{g(x)^{n+1}}\right)&=\operatorname{res}\left(\left(\frac{\Phi(x)}{g(x)^n}\right)'\right) \\
&=0
\end{aligned} res ( g ( x ) n Φ ′ ( x ) − n g ( x ) n + 1 Φ ( x ) g ′ ( x ) ) = res ( ( g ( x ) n Φ ( x ) ) ′ ) = 0 so this follows from what we have already proved.
References
Richard P. Stanley and Sergey P. Fomin. Enumerative Combinatorics Volume 2 (Edition 1).
Ira M. Gessel. Lagrange Inversion.