Lagrangeの反転公式

同義語:Lagrange inversion formulaLagrangeの反転定理Lagrange inversion theoremLagrange–Bürmannの公式Lagrange–Bürmann formula

概要

Lagrangeの反転公式(Lagrange inversion formula)とは、標数 $0$ の体の上で $\varphi(0)\ne0$ となる形式的冪級数 $\varphi$ について、方程式 $f=x\varphi(f)$ のただ 1 つの解 $f$ の係数を $[x^n]f^k=\frac kn[t^{n-k}]\varphi(t)^n$($n\ge1$)と $\varphi$ の冪の係数で表す公式である。関数 $y/\varphi(y)$ の合成の逆の展開を与え、形式的 Laurent 級数の留数の計算で証明できる。根と部分木への再帰で定まる木の母関数はこの形の方程式を満たすので、ラベル付き根付き木が $n^{n-1}$ 個あること(Cayley の公式)や、平面木が Catalan 数だけあることが直ちに従う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 形式的冪級数, 母関数

Lagrange の反転公式(Lagrange inversion formula)は、方程式 $f=x\,\varphi(f)$ で決まる形式的冪級数 $f(x)$ の係数を、与えられた級数 $\varphi$ の冪の係数で表す公式
$$ [x^n]f(x)=\frac1n\,[t^{n-1}]\,\varphi(t)^n $$
である。$[x^n]F$ は $F$ の $x^n$ の係数を表す。$y=x\varphi(y)$ は $x=y/\varphi(y)$ と同じことなので、この公式は関数 $y\mapsto y/\varphi(y)$ の逆関数の展開係数を与える式でもある。
組合せ論では、木のように「根と、その下にぶら下がる同じ種類の構造の集まり」として再帰的に定義される対象の母関数が、ちょうど $f=x\varphi(f)$ の形の方程式を満たす。反転公式はその方程式を解かずに係数だけを取り出す。たとえば $\{1,\dots,n\}$ を頂点とする根付き木の個数が $n^{n-1}$ であること(Cayleyの公式 の根付きの形)は、$\varphi(t)=e^t$ に反転公式を当てるだけで得られる。
この記事では、形式的 Laurent 級数の留数を使って反転公式(冪 $f^k$ についての Bürmann の形を含む)を完全に証明する。続いて、ラベル付き根付き木と根付き森、平面木の数え上げに応用し、全数で検算する。最後に、仮定を外すと何が成り立たなくなるかを反例の表にまとめる。

設定と記号

以下、$K$ を標数 $0$ の体($\mathbb Q$、$\mathbb R$、$\mathbb C$ など)とする。$K[\![x]\!]$ は $K$ 係数の形式的冪級数の環である。

形式的 Laurent 級数・微分・留数

有限個を除いて負の冪の係数が $0$ である形式的な和 $F=\sum_{m\ge m_0}c_mx^m$($m_0\in\mathbb Z$)を 形式的 Laurent 級数 といい、その全体を $K(\!(x)\!)$ と書く。和と積は冪級数と同様に定め、$K(\!(x)\!)$ は体になる。$F$ の 形式的微分 を $F':=\sum_m mc_mx^{m-1}$、留数 を $\operatorname{res}F:=c_{-1}=[x^{-1}]F$ と定める。

$F\ne0$ のとき、$c_m\ne0$ となる最小の $m$ を $F$ の 位数 という。定数項が $0$ で $x$ の係数が $0$ でない級数 $g\in K[\![t]\!]$ は $g=t\,u(t)$、$u(0)\ne0$ と書け、$u$ は $K[\![t]\!]$ の単元なので、すべての整数 $m$ について $g^m=t^mu^m$ は位数がちょうど $m$ の Laurent 級数である。そこで $F=\sum_mc_mx^m\in K(\!(x)\!)$ に $g$ を 代入 した $F(g):=\sum_mc_mg^m\in K(\!(t)\!)$ が定まる。$t^N$ の係数には $m\le N$ の有限個の項しか寄与しないからである。

留数と微分・代入の規則

$F,G\in K(\!(x)\!)$ と、$g=t\,u(t)$($u(0)\ne0$)について次が成り立つ。

  1. $\operatorname{res}(F')=0$。
  2. $F\mapsto F(g)$ は環の準同型であり、$(F(g))'=F'(g)\,g'$(連鎖律)。
  3. 整数 $m\ne0$ について $\operatorname{res}(g^{m-1}g')=0$、また $\operatorname{res}(g'/g)=1$。
証明を開く

1:$(x^m)'=mx^{m-1}$ なので、$x^{-1}$ の係数は $m=0$ の項からしか生じず、その係数は $0\cdot c_0=0$ である。

2:$F(g)$ の $t^N$ の係数は、$F$ の $m\le N$ の項だけで決まる。$F,G$ を十分高い次数で切った Laurent 多項式に置き換えても $t^N$ の係数は変わらないので、Laurent 多項式について示せばよい。Laurent 多項式では、和と積が保たれるのは $g^ag^b=g^{a+b}$ による。連鎖律は単項式 $x^m$ について $(g^m)'=mg^{m-1}g'$ を示せば足りる。$m\ge0$ は積の微分法則と帰納法で従い、$m< 0$ は $g^mg^{-m}=1$ を微分して $(g^m)'g^{-m}+g^m(-m)g^{-m-1}g'=0$ を解けばよい。微分は係数ごとの操作なので、切り詰めと交換する。

3:$m\ne0$ なら 2 により $g^{m-1}g'=(g^m)'/m$ で、1 から留数は $0$ である。また $g=tu$ から $g'/g=1/t+u'/u$ で、$u'/u\in K[\![t]\!]$ なので留数は $1$ である。$\square$

主定理

Lagrange の反転公式

$\varphi\in K[\![t]\!]$ を $\varphi(0)\ne0$ とする。

  1. $f=x\,\varphi(f)$ を満たす $f\in xK[\![x]\!]$ がただ 1 つ存在し、$[x^1]f=\varphi(0)$ である。
  2. $n\ge1$ とすべての整数 $k$ について
    $$ n\,[x^n]f^k=k\,[t^{n-k}]\varphi(t)^n $$
    が成り立つ($k\le0$ では $f^k\in K(\!(x)\!)$)。とくに $[x^n]f=\frac1n[t^{n-1}]\varphi(t)^n$ である。
  3. 任意の $H\in K[\![t]\!]$ と $n\ge1$ について $n\,[x^n]H(f)=[t^{n-1}]H'(t)\varphi(t)^n$ である。

2 の冪についての形は Bürmann の形ともよばれる(FS09 Appendix A.6、Theorem A.2、p. 732)。同書は $\mathbb C$ 係数の場合を Cauchy の積分公式による変数変換で証明している。ここでは複素解析を使わず、留数の形式的な計算だけで証明する。

逆関数を代入して留数をとる

1:$f=\sum_{m\ge1}f_mx^m$ とおく。$\varphi(f)=\sum_j\varphi_jf^j$ の $x^{n-1}$ の係数は、$f^j$ の位数が $j$ 以上なので $j\le n-1$ の有限個の項から来て、$f_1,\dots,f_{n-1}$ だけで決まる。よって $f=x\varphi(f)$ の $x^n$ の係数の式 $f_n=[x^{n-1}]\varphi(f)$ は、$f_1=\varphi_0$ から始めて $f_n$ を順に一意に定める。
2:$g(t):=t/\varphi(t)$ とおくと $g=t\,u(t)$、$u=1/\varphi$、$u(0)=1/\varphi(0)\ne0$ である。まず $f(g(t))=t$ を示す。$h:=f(g)\in tK[\![t]\!]$ とおく。$f=x\varphi(f)$ に $x=g$ を代入すると(lem-li-rules の 2)、$h=g\cdot\varphi(h)$、すなわち $h/\varphi(h)=t/\varphi(t)$ である。$\psi(s):=s/\varphi(s)$ とおくと $\psi(h)=\psi(t)$ である。$h\ne t$ と仮定し、$h$ と $t$ の係数が最初に異なる次数を $N$ とする。$\psi(s)=\sum_{j\ge1}a_js^j$($a_1=1/\varphi(0)\ne0$)と書くと、$h^j-t^j$ は $h-t$ で割り切れ、$j\ge2$ では商の位数が $1$ 以上なので、$h^j-t^j$ の位数は $N+1$ 以上である。よって $\psi(h)-\psi(t)$ の $t^N$ の係数は $a_1([t^N]h-[t^N]t)\ne0$ となり矛盾する。したがって $h=t$ である。
次に $c_m:=[x^m]f^k$ とおき、$f^k=\sum_{m\ge k}c_mx^m$ と書く($f$ の位数は $1$ なので $f^k$ の位数は $k$)。これに $x=g$ を代入すると、準同型性から
$$ t^k=f(g)^k=\sum_{m\ge k}c_m\,g^m $$
である。両辺を微分すると、連鎖律(lem-li-rules の 2)から
$$ k\,t^{k-1}=\sum_{m\ge k}m\,c_m\,g^{m-1}g' $$
となる。両辺に $g^{-n}$ を掛けて留数をとる。右辺の和は各次数で有限なので、留数は項ごとにとってよい。$m\ne n$ の項は $\operatorname{res}(g^{m-n-1}g')=0$、$m=n$ の項は $\operatorname{res}(g'/g)=1$ である(lem-li-rules の 3)。よって右辺の留数は $n\,c_n$ である。左辺は $g^{-n}=t^{-n}\varphi(t)^n$ なので
$$ \operatorname{res}\bigl(k\,t^{k-1-n}\varphi(t)^n\bigr)=k\,[t^{n-k}]\varphi(t)^n $$
である。したがって $n\,c_n=k\,[t^{n-k}]\varphi^n$ が成り立つ。$n< k$ のときは両辺とも $0$ である($f^k$ の位数は $k$ で、$t^{n-k}$ は負の冪)。
3:$H=\sum_{k\ge0}h_kt^k$ とすると $H(f)=\sum_kh_kf^k$ で、$x^n$ の係数には $k\le n$ の項だけが寄与する。2 を $k=0,\dots,n$ について足すと $n[x^n]H(f)=\sum_kkh_k[t^{n-k}]\varphi^n=[t^{n-1}]H'\varphi^n$ である($H'=\sum_kkh_kt^{k-1}$)。$\square$

$\varphi(0)=0$ の場合は $f=0$ が唯一の解で、$\varphi^n$ の位数が $n$ 以上なので 2 の右辺も $k\ge1$ では $0$ になり、公式は自明に成り立つ。仮定 $\varphi(0)\ne0$ は、$f$ が $0$ でなく $g=t/\varphi(t)$ が定まるために置いている。

例:合成の逆

$x+x^2$ の合成の逆

$g+g^2=x$ を満たす $g\in xK[\![x]\!]$ を求める。$g(1+g)=x$ は $g=x\cdot\frac{1}{1+g}$ と同じなので、$\varphi(t)=(1+t)^{-1}$ とおける。反転公式と一般二項定理 $[t^{n-1}](1+t)^{-n}=(-1)^{n-1}\binom{2n-2}{n-1}$ から
$$ [x^n]g=\frac{(-1)^{n-1}}{n}\binom{2n-2}{n-1}=(-1)^{n-1}C_{n-1} $$
である($C_m$ は Catalan数)。よって $g=x-x^2+2x^3-5x^4+14x^5-\cdots$ で、これは 形式的冪級数 の記事が係数を次数ごとに解いて得た展開の始まりと一致する。

一般に、$F(y)=a_1y+a_2y^2+\cdots$($a_1\ne0$)の合成の逆 $y(x)$ は、$\varphi(y):=y/F(y)$ とおけば $y=x\varphi(y)$ を満たすので、$[x^n]y=\frac1n[t^{n-1}](t/F(t))^n$ で求まる。

木の数え上げ

ラベル付き根付き木と Cayley の公式

頂点集合 $\{1,\dots,n\}$ 上の木と、根とよぶ 1 頂点の組を ラベル付き根付き木 という(根付き木)。その個数を $r_n$ とし、指数型母関数 $R(x):=\sum_{n\ge1}r_n\,x^n/n!$ を考える(母関数)。

根付き木の母関数の方程式

$R(x)=x\,e^{R(x)}$ が $K[\![x]\!]$ で成り立つ。

根を外して部分木の集合に分ける

根 $v$ を外すと、ラベル付き根付き木は、$v$ の子をそれぞれ根とする根付き木の集合に分かれる。逆に、根のラベル $v$ と、残りのラベル $\{1,\dots,n\}\setminus\{v\}$ を $j$ 個の空でない組に分けて各組に根付き木を載せたものを与えれば、各根を $v$ に結んで根付き木が 1 つ決まる。2 つの操作は互いに逆である。したがって
$$ r_n=n\sum_{j\ge0}\frac{1}{j!}\sum_{n_1+\cdots+n_j=n-1}\binom{n-1}{n_1,\dots,n_j}r_{n_1}\cdots r_{n_j} $$
である($n_i\ge1$)。内側の和は、ラベルの組を並べる順序まで区別して数えたもので、組は空でなく互いに交わらないので、同じ集合がちょうど $j!$ 回数えられる。一方、指数型母関数の積の係数は
$$ [x^{n-1}]\frac{R^j}{j!}=\frac{1}{j!}\sum_{n_1+\cdots+n_j=n-1}\frac{r_{n_1}\cdots r_{n_j}}{n_1!\cdots n_j!} $$
であり、これに $(n-1)!$ を掛けると内側の和の $1/j!$ 倍に等しい。よって $r_n/n!=\frac{n}{n!}(n-1)!\sum_j[x^{n-1}]R^j/j!=[x^{n-1}]e^R$、すなわち $[x^n]R=[x^n](xe^R)$ である。$\square$

根付き木と根付き森の個数

$n\ge1$ とする。

  1. $\{1,\dots,n\}$ 上のラベル付き根付き木は $n^{n-1}$ 個、ラベル付き木は $n^{n-2}$ 個ある。
  2. $1\le k\le n$ について、$\{1,\dots,n\}$ を頂点とし、ちょうど $k$ 個の根付き木からなる根付き森は $\binom{n-1}{k-1}n^{n-k}$ 個ある。

prop-li-tree-eq により $R$ は $\varphi(t)=e^t$ に対する thm-li-main の $f$ である。$[t^{n-k}]e^{nt}=n^{n-k}/(n-k)!$ なので
$$ [x^n]R^k=\frac kn\cdot\frac{n^{n-k}}{(n-k)!} $$
である。$k=1$ では $r_n=n!\,[x^n]R=(n-1)!\,n^{n-1}/(n-1)!=n^{n-1}$ を得る。各木には根の選び方が $n$ 通りあるので、ラベル付き木の個数は $n^{n-1}/n=n^{n-2}$ である。
2:$k$ 個の根付き木の森は、頂点集合を $k$ 個の空でない組に分け、各組に根付き木を載せたものである。prf-li-tree-eq と同じ数え方により、その個数は $n!\,[x^n]R^k/k!$ である。上の式を代入すると
$$ \frac{n!}{k!}\cdot\frac kn\cdot\frac{n^{n-k}}{(n-k)!}=\frac{(n-1)!}{(k-1)!\,(n-k)!}\,n^{n-k}=\binom{n-1}{k-1}n^{n-k} $$
である。$\square$

$n$$1$$2$$3$$4$$5$
根付き木 $n^{n-1}$$1$$2$$9$$64$$625$
木 $n^{n-2}$$1$$1$$3$$16$$125$

$n=4$ の根付き森は、木の個数 $k=1,2,3,4$ ごとに $64,48,12,1$ 個である。合計 $125=5^3$ は、各根を新しい頂点 $5$ に結ぶ対応により、$5$ 頂点のラベル付き木の個数に等しい。$n\le6$ について、各頂点の親を選ぶ写像を全部調べ、根付き木と根付き森の個数が上の式に一致することを確かめた。Prüfer 符号による全単射の証明は Cayleyの公式 の記事にある。FS09 も同じ方程式 $T=ze^T$ に反転公式を当てて $n^{n-1}$ を導いている(§II.5、式 (44)–(47)、p. 127)。

平面木と Catalan 数

子に左から順序の付いた根付き木を、ラベルを付けずに数える。これを 平面木(順序付き根付き木)という。頂点数 $n$ の平面木の個数を $p_n$ とし、通常の母関数 $P(x)=\sum_{n\ge1}p_nx^n$ を考える。

平面木の個数

$P=x/(1-P)$ であり、$p_n=\frac1n\binom{2n-2}{n-1}=C_{n-1}$ である。

証明を開く

平面木は、根と、その子を根とする平面木の列(長さ $0$ 以上)の組と一対一に対応する。列なので並べる順序は区別され、頂点数が $n_1,\dots,n_j$ の列の数は $p_{n_1}\cdots p_{n_j}$ である。よって $P=x(1+P+P^2+\cdots)=x/(1-P)$ であり、$P$ は $\varphi(t)=(1-t)^{-1}$ に対する $f$ である。$[t^{n-1}](1-t)^{-n}=\binom{2n-2}{n-1}$ なので、反転公式から $p_n=\frac1n\binom{2n-2}{n-1}$ である。$\square$

同じ方法で、子の個数に制限のある木も数えられる。$\varphi$ を「頂点がとれる子の配置の母関数」に選べばよい。

$\varphi(t)$数える木$n=1,\dots,8$ の個数
$e^t$(指数型)ラベル付き根付き木($n!$ 倍して)$1,2,9,64,625,7776,117649,2097152$
$(1-t)^{-1}$平面木$1,1,2,5,14,42,132,429$
$1+t^2$子が $0$ 個か $2$ 個の平面木$1,0,1,0,2,0,5,0$
$1+t+t^2$子が $2$ 個以下の平面木$1,1,2,4,9,21,51,127$
$(1+t)^2$各頂点に左右 $2$ つの子の枠がある二分木$1,2,5,14,42,132,429,1430$

最後の行の二分木は、各頂点の左の枠と右の枠のそれぞれに子を置くか置かないかを選ぶので $\varphi=(1+t)^2$ であり、反転公式から個数は $\frac1n\binom{2n}{n-1}=C_n$ である(二分木)。3 行目は頂点数 $2i+1$ で $C_i$ になる。表の値はすべて、方程式 $f=x\varphi(f)$ を係数ごとに解いた値と反転公式の値の両方で計算して一致を確かめた。平面木の数え上げは、前置記法の項の数え上げと同じものであり、巡回補題による組合せ的な証明は反転公式と同値な内容をもつ(ポーランド記法、FS09 Note I.47、pp. 75–76)。

応用

  • 木と写像の数え上げ:根と部分木への再帰で定まる族(FS09 は simple variety of trees とよぶ。Proposition I.5、p. 66)の個数は、すべて反転公式で $\varphi$ の冪の係数に帰着する。写像 $\{1,\dots,n\}\to\{1,\dots,n\}$ の個数 $n^n$ を木の母関数から読み直すこともできる(同 Note A.13、p. 733)。
  • 漸近解析:$\varphi$ の冪の係数は鞍点法などで評価しやすいので、反転公式は木の個数の漸近評価の出発点になる(解析的組合せ論)。
  • 合成の逆と恒等式:級数の合成の逆の係数を閉じた形で与えるほか、Abel の恒等式のような二項係数の恒等式を、同じ係数を 2 通りに計算して導く道具になる(FS09 Note A.12、p. 733)。

反例の表

外す条件例成り立たなくなること
係数体の標数が $0$$\mathbb F_2$ 上で $\varphi=1+t$$[x^2]f$ を $\frac12[t]\varphi^2$ として求めること($2$ で割れない)
$\varphi$ が冪級数(負の冪がない)$\varphi(t)=t^{-1}$解 $f\in xK[\![x]\!]$ の存在(1)
数える対象にラベルを付ける根付き木を同型類で数える個数が $n!\,[x^n]R=n^{n-1}$ になること
子の順序を区別する(平面木)子の順序を区別しない根付き木を通常の母関数で数える方程式 $P=x/(1-P)$ と個数 $C_{n-1}$
反例の確認

1 行目:$f=x(1+f)$ の解は $f=x+x^2+x^3+\cdots$ で、どの体でも $[x^2]f=1$ である。公式 2 の形 $2[x^2]f=[t](1+t)^2=2$ は $\mathbb F_2$ でも成り立つが、両辺が $0$ になるので $[x^2]f$ を決めない。$n$ で割る形の公式は標数 $0$(または $n$ が係数体で可逆)を必要とする。
2 行目:$f=x\cdot f^{-1}$ は $f^2=x$ と同じである。$f\in xK[\![x]\!]$ なら $f^2$ の位数は $2$ 以上で、位数 $1$ の $x$ と等しくなれないので、解は存在しない。
3 行目:根付き木の同型類は頂点数 $1,\dots,5$ で $1,1,2,4,9$ 個である(全数で数えた)。$n^{n-1}/n!$ は $1,1,3/2,8/3,125/24$ で、整数でさえない。同型類を数えると prf-li-tree-eq の「ラベルの組の分け方」の数え方が成り立たず、方程式 $R=xe^R$ が導かれない。
4 行目:子の順序を区別しないと、頂点数 $3$ の木は「根に子が 2 つ」と「根・子・孫の 1 本道」の $2$ 個で、平面木の $C_2=2$ と一致するが、頂点数 $4$ では $4$ 個で $C_3=5$ と異なる(根に子が 3 つ、子が 2 つでその一方に孫、1 本道、子が 1 つで孫が 2 つ)。平面木では「子が 2 つでその一方に孫」が左右の 2 通りに分かれる。

関連項目

参考文献

[1]
Philippe Flajolet, Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, §I.5 Proposition I.5 と Lagrange Inversion Theorem の式 (69)(p. 66)、Note I.47(pp. 75–76)、§II.5 式 (44)–(47)(p. 127)、Appendix A.6 Theorem A.2(p. 732)、Notes A.12・A.13(p. 733)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する