Lagrange 反転変種チートシート

関連記事

Lagrange inversion theorem - Codeforces

[Tutorial] Generating Functions in Competitive Programming (Part 2) - Codeforces

公式集

注意: 一応証明したつもりですが、係数環を一般の可換環に取るところが怪しいです

• : 可換環
• 
• 
• 
• 
• 

逆関数の係数

\begin{alignat}{2} \lbrack x ^ n \rbrack G(x) & {} = \frac{1}{n} & \lbrack x ^ {- 1} \rbrack & F(x) ^ {- n} \cr & = {} & \lbrack x ^ {- 2} \rbrack & F(x) ^ {- n - 1} F'(x) \cr & = \frac{1}{n} & \lbrack x ^ {n - 1} \rbrack & \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n - 1} \rbrack & \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

逆関数の冪乗の係数

\begin{alignat}{2} \lbrack x ^ n \rbrack G(x) ^ k & {} = \frac{k}{n} & \lbrack x ^ {- k} \rbrack & F(x) ^ {- n} \cr & = {} & \lbrack x ^ {- k - 1} \rbrack & F(x) ^ {- n - 1} F'(x) \cr & = \frac{k}{n} & \lbrack x ^ {n - k} \rbrack & \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n - k} \rbrack & \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

逆関数との合成

\begin{alignat}{2} \lbrack x ^ n \rbrack H(G(x) ) & {} = \frac{1}{n} & \lbrack x ^ {-1} \rbrack & H'(x) F(x) ^ {- n} \cr & = {} & \lbrack x ^ {-1} \rbrack & H(x) F(x) ^ {- n - 1} F'(x) \cr & = \frac{1}{n} & \lbrack x ^ {n - 1} \rbrack & H'(x) \phi(x) ^ {n} \cr & = {} & \lbrack x ^ {n} \rbrack & H(x) \phi(x) ^ {n - 1} (\phi(x) - x \phi'(x) ) \end{alignat}

さらに一般化したもの

について

\begin{alignat}{2} \lbrack x ^ {- 1} \rbrack W(x) H(G(x) ) = \lbrack x ^ {-1} \rbrack & W(F(x) ) H(x) F'(x) \end{alignat}

証明

補題

\begin{align} \lbrack x ^ {- 1} \rbrack F(x) ^ n F'(x) = \begin{cases} 1 \quad & (n = - 1) \cr 0 \quad & (n \neq - 1) \end{cases} \end{align}

倍を含む形式

\begin{align} G(F(x) ) &= x \cr H(G(F(x))) &= H(x) \cr (H \circ G)'(F(x)) F'(x) &= H'(x) \cr (H \circ G)'(F(x)) F(x) ^ {- n} F'(x) &= H'(x) F(x) ^ {- n} \cr \lbrack x ^ {-1} \rbrack (H \circ G)'(F(x)) F(x) ^ {- n} F'(x) &= \lbrack x ^ {-1} \rbrack H'(x) F(x) ^ {- n} \cr n \lbrack x ^ n \rbrack H(G(x) ) &= \lbrack x ^ {-1} \rbrack H'(x) F(x) ^ {- n} \cr \end{align}

倍を含まない形式

\begin{align} G(F(x) ) &= x \cr H(G(F(x))) &= H(x) \cr H(G(F(x) ) ) F(x) ^ {- n - 1} F'(x) &= H(x) F(x) ^ {- n - 1} F'(x) \cr \lbrack x ^ {-1} \rbrack H(G(F(x) ) ) F(x) ^ {- n - 1} F'(x) &= \lbrack x ^ {-1} \rbrack H(x) F(x) ^ {- n - 1} F'(x) \cr \lbrack x ^ n \rbrack H(G(x) ) &= \lbrack x ^ {-1} \rbrack H(x) F(x) ^ {- n - 1} F'(x) \cr \end{align}