Lagrange inversion theorem

發表於 2021-10-09 更新於 2024-10-23 分類於 algorithm Disqus：文章字數： 995 所需閱讀時間 ≈ 3 分鐘

拉格朗日反演

Lagrange inversion theorem 拉格朗日反演

解决的问题

给定F(x), 找G(x) 使得 G(F(x)) = x, 也就是找反函数

这里有一点要用到,但是没有证明的是 $G (F (x)) = x$ 则 $F (G (x)) = x$ , 只能说在 $F (x)$ 的值域内 $F (G (F (x)) = F (x)$ 即 $F (G (x)) = x$ 可以证明, 但在值域外不知道如何证明…

结论

如果 $F, G$ 满足

0次项系数均为0: $[x^{0}] F (x) = [x^{0}] G (x) = 0$
1次项系数均非0: $[x^{1}] F (x) \neq 0, [x^{1}] G (x) \neq 0$

那么 $[x^{n}] G (x)^{k} = \frac{k}{n} [x^{n - k}] {(\frac{x}{F (x)})}^{n} .$

$[x^{n}] G (x) = \frac{1}{n} [x^{n - 1}] {(\frac{x}{F (x)})}^{n} .$

证明

辅助lemma: 任何 $F (0) = 0$ (0次系数为0), $F^{'} (0) \neq 0$ (?存在非0次的非0系数?????), 有对于 $\forall k \in Z$

$[x^{- 1}] F^{'} (x) F (x)^{k} = [k = - 1]$

即 $k = - 1$ 时 $- 1$ 次系数为 $1$ ,否则 $- 1$ 次系数为 $0$

证明lemma:

对于 $k \neq - 1$ , 显然求导法则 $F^{'} (x) F (x)^{k} = \frac{{(F (x)^{k + 1})}^{'}}{k + 1}$ , 所以 $\leq 0$ 的x的幂次的系数都是0

对于 $k = - 1$ , $F (x) = \sum_{i > 0} a_{i} x^{i}$

$\frac{F^{'} (x)}{F (x)} = \frac{a_{1} + 2 a_{2} x + 3 a_{3} x^{2} + \dots}{x (a_{1} + a_{2} x + a_{3} x^{2} + \dots} = x^{- 1} \frac{1 + 2 \frac{a_{2}}{a_{1}} x + \dots}{1 + \frac{a_{2}}{a_{1}} x + \dots}$

也就是右侧这个分式除完以后是 $1 + k_{1} x + k_{2} x^{2} + \dots$ 的样子, 因此 -1 次方的系数是 1, lemma 证毕.

这里注意到像 $\frac{1}{1 - x}$ 这种对应的 $x^{- 1}$ 的系数是0,因为它虽然写在分母上，但实际是泰勒展开到正，而 $\frac{1}{x}$ 是不能在0点泰勒展开成正的?而去查 1/x的泰勒展开，都是在点1的展开

因此 $G (F (x))^{k} = x^{k}, k \geq 1, k \in Z$ , 的 $G$ 满足条件

$(\sum_{i} ([x^{i}] G^{k} (x)) F (x)^{i})^{'} \cdot F^{'} (x) = k x^{k - 1}$ ( 同时对 $x$ 求导, 以及按位展开式 $G^{k} (x) = \sum_{i} ([x^{i}] G^{k} (x)) x^{i}$

展开 $\sum_{i} i ([x^{i}] G^{k} (x)) F (x)^{i - 1} F^{'} (x) = k x^{k - 1}$ , (基本的求导法则 $(a x^{i})^{'} = i a x^{i - 1}$ , 注意到前两项都是常系数而非生成函数

$\sum_{i} i ([x^{i}] G^{k} (x)) F^{i - 1 - n} (x) F^{'} (x) = k x^{k - 1} F^{- n} (x) .$ ( 同乘上 $F^{- n}$ , 这里想用lemma, 也就是 $[x^{- 1}] F^{?} (x) F^{'} (x)$ , 同时最终目标是 $[x^{?}] G (x)$

$[x^{- 1}] (\sum_{i} i ([x^{i}] G^{k} (x)) F^{i - 1 - n} (x) F^{'} (x)) = [x^{- 1}] (k x^{k - 1} F^{- n} (x)) .$ (提取 $- 1$ 次项目的系数

因为左侧 $i ([x^{i}] G (x))$ 整个都是系数, 以及上面的lemma, 左侧只有 $i - 1 - n = - 1$ 即 $i = n$ 时, $[x^{- 1}] F^{i - 1 - n} (x) F^{'} (x)$ 生成系数的内容才为 $1$ ,其它则是 $0$ ,

$n [x^{n}] G^{k} (x) = [x^{- 1}] k x^{k - 1} F^{- n} (x)$

变形一下,就有了最初要证明的 $[x^{n}] G (x) = \frac{k}{n} [x^{n - k}] {(\frac{x}{F (x)})}^{n} .$

这玩意百科上说建立了函数方程和幂级数之间的联系 !!??

使用示例: 卡特兰数Catalan number

$c_{0} = 1$

$c_{n + 1} = \sum_{i = 0}^{n} c_{i} \cdot c_{n - i}$

令 $C$ 为以卡特兰数 1,1,2,5,14为系数的生成方程

令 $F (x) = C (x) - 1$ , 保证0次项系数为0, 1次系数非0

那么 $F (x) = x (F (x) + 1)^{2}$ , 根据卡特兰数本身推导的定义的到的

令 $G (x) = \frac{x}{(x + 1)^{2}}$

那么有 $G (F (x)) = \frac{F (x)}{(F (x) + 1)^{2}} = x$

那么 $c_{n}$ 就有了

因此

$\begin{aligned} F (x) & = \frac{1}{n} [x^{n - 1}] {(\frac{x}{G (x)})}^{n} \\ = \frac{1}{n} [x^{n - 1}] (x + 1)^{2 n} \\ = \frac{1}{n} (\binom{2 n}{n - 1}) = \frac{1}{n + 1} (\binom{2 n}{n}), \end{aligned}$

Lagrange inversion theorem 拉格朗日反演

解决的问题

结论

证明

使用示例: 卡特兰数Catalan number

相关