ページ

2013年2月25日月曜日

Lagrange Invertion Theoremの説明

やあ、みんな。

Lagrange Inversion Theoremについて語ってみるよ。

参考:Lagrange inversion theorem - Wikipedia, the free encyclopedia

いままで逆元といえば、コーシー積に関する逆元を計算してきたね。ここで単位元は1という「級数」だった。

合成積における逆元(Composition Inverse)というのは、合成積の結果XになるFPSの元のことなんだ。つまり、
\[
g(f(X)) = X
\]
gはfに対するComposition Inverseになってる。Lagrange Inversion Theorem(LIT)というのはこれを計算するための公式だよ。



(注意:fは何でもいいというわけではなくて、定数項が0のものに限られる。)

Lagrange Inversion Theorem

逆関数(inversion)。

\[
[X^{k}] f^{-1}(X)^{n} = \frac{n}{k}[X^{k-n}] \left( \frac{X}{f(X)} \right)^{k}= \frac{n}{k}[X^{k-n}] \phi(X)^{k}
\tag{1}
\]

(1)式をもっと一般的にすると(Lagrange–Bürmann公式と言われてる)、

\[
[X^{k}] G(f^{-1}(X)) = \frac{1}{k}[X^{k-1}] G^{\prime}(X) \phi(X)^{k}
\tag{2}
\]

(1)式の右辺についてテイラー展開するとこうなるよ(ラグランジェ展開とも呼ばれてるみたい)。

\[
[X^{k}] f^{-1}(X)^{n} = \frac{n}{k}[X^{k-n}] \sum_{i=0}^{\infty} \left\{ \frac{d^{i}}{dX^{i}}\phi(X)^{k} \right\}_{X \to 0} \frac{X^{i}}{i!}
\]
\[
=\frac{n}{k} \left\{ \frac{d^{k-n}}{dX^{k-n}}\phi(X)^{k} \right\}_{X \to 0} \frac{1}{(k-n)!}
\tag{3}
\]
証明

出来るだけ簡単な証明、ってことで、ここではR.Stanley(2001), "Enumerative combinatorics 2"のchapter 5.4の記述を参考にしたよ。

まず考えるFPSの範囲だけど、添字は必ずしも非負整数じゃないよ。マイナスの項も考えるのさ。これは形式的ローレント級数(Formal Laurent Series)と呼ばれているよ。

次に重要なことは、k=-1の項は特別っていうことだよ。微分すると普通は次数が下がるだけだけど、唯一の例外はk=0のところさ。微分しても0になるだけで-1次に下がるわけじゃないよね。とても不思議だけど、この証明はその事実に依存しているんだ。だからFPSを微分して-1項目を見ると必ず0になってる。

\[
[X^{-1}] y^{\prime} = 0
\]

まず、考えている逆関数がべき級数でこんな風に表現できると考えてみよう。

\[
f^{-1}(X)^{n} = \sum_{i \geq k} p_{i}X^{i}
\]
ここでX=f(X)を代入しちゃう。
\[
X^{n} = \sum_{i \geq k} p_{i} f(X)^{i}
\]
両辺を微分。
\[
n X^{n-1} = \sum_{i \geq k} i p_{i} f(X)^{i-1} f^{\prime}(X)
\]
両辺をf(X)^kで割り算。
\[
\frac{n X^{n-1}}{f(X)^{k}} = \sum_{i \geq k} i p_{i} f(X)^{i-k-1} f^{\prime}(X)
\tag{4}
\]
ここで両辺の-1項目をとるよ。
ところで、i=kを除いて、
\[
f(X)^{i-k-1}f^{\prime}(X) = \frac{1}{i-k} \left( f(X)^{i-k} \right)^{\prime}
\]
と表現できるから、右辺は-1項目で残るのはi=kの場合だけ。だから(4)式の-1項目は、
\[
[X^{-1}] k p_{k}f(X)^{-1}f^{\prime}(X)
\]
ところで、f(X)を下のように表してみよう。
\[
f(X) = a_{1}X + a_{2}X^{2} + \cdots = X(a_{1} + a_{2}X + a_{3}X^{2} + \cdots) = Xh(X)
\]
すると、
\[
\frac{f^{\prime}(X)}{f(X)} = \frac{h(X) + Xh^{\prime}(X)}{Xh(X)}=\frac{1}{X} + \frac{h^{\prime}(X)}{h(X)}
\]
だから、
\[
[X^{-1}] k p_{k}f(X)^{-1}f^{\prime}(X) = k p_{k} [X^{-1}] \left( \frac{1}{X} + \frac{h^{\prime}(X)}{h(X)} \right) = k p_{k}
\]
整理するとこうなる。
\[
[X^{-1}] \frac{n X^{n-1}}{f(X)^{k}} = k p_{k}
\tag{5}
\]

(5)式の右辺は、
\[
k p_{k} = k[X^{k}]f^{-1}(X)^{n}
\]

(5)式の左辺は、
\[
[X^{-1}] \frac{n X^{n-1}}{f(X)^{k}} = [X^{-1}] nX^{n-k-1} \left( \frac{X}{f(X)} \right)^{k} = n [X^{k-n}] \left( \frac{X}{f(X)} \right)^{k}
\]

合わせて、
\[
k [X^{k}] f^{-1}(X)^{n} = n[X^{k-n}] \left( \frac{X}{f(X)} \right)^{k}
\]

力尽きた。応用についてはまた今度

じゃあ、またね。