§E13.20Lagrange の反転公式

最終更新

数え上げでは、母関数が閉じた式ではなく関数方程式によって与えられることが多い。根付き平面木の母関数T(x)T(x)はT=x/(1−T)T=x/(1-T)を満たし、Catalan 数の母関数C(x)C(x)はC=1+xC2C=1+xC^{2}を満たす。方程式を「解く」ことなく係数だけを取り出すことができれば、閉じた式を経由せずに数え上げの答えが得られる。

Lagrange–Bürmann の係数公式は、まさにこの操作を与える。WWがW=x ϕ(W)W=x\,\phi(W)を満たすとき、WWの第nn係数はϕ(x)n\phi(x)^{n}の第n−1n-1係数をnnで割ったものに等しい。この主張を形式的に述べ、証明するには、形式的冪級数の合成、形式微分、および負べきを許した級数における留数を定義しなければならない。先行記事は形式的冪級数の和、積、位数および総和可能な族までを与えているが、合成も形式微分も与えていない。本記事はこれらを定義したうえで、合成逆元の存在と一意性、係数公式、そして Catalan 数と根付き平面木への適用を証明する。

1 形式的冪級数の可逆元

係数体は有理数体Q\mathbb Qとする。形式的冪級数の和、Cauchy 積および係数抽出[xn][x^{n}]の定義は§D2.4 定義 4.1と§E13.1 定義 1.1が、これらの演算が単位元をもつ可換環を定めることは§E13.1 命題 1.2が、位数ord⁡\operatorname{ord}の定義は§E13.2 定義 2.1が、総和可能な族の定義は§E13.2 定義 2.3が与える。位数が積で加わることは§E13.2 補題 2.2による。本記事では、負べきを許す級数まで扱うため、位数と総和可能性の定義を後で拡張する。

定理 1.1.F∈Q[[x]]F\in\mathbb Q[[x]]がQ[[x]]\mathbb Q[[x]]の可逆元であることと、[x0]F≠0[x^{0}]F\ne0であることは同値である。逆元は存在すれば一意である。

証明. 必要性。FG=1FG=1ならば、Cauchy 積の定数項をとって([x0]F)([x0]G)=1([x^{0}]F)([x^{0}]G)=1であるから[x0]F≠0[x^{0}]F\ne0である。

十分性。fn=[xn]Ff_n=[x^{n}]Fと書き、f0≠0f_0\ne0とする。有理数の列(gn)n≥0(g_n)_{n\ge0}を

g0=f0−1,gn=−f0−1∑j=1nfj gn−j(n≥1)g_0=f_0^{-1},\qquad g_n=-f_0^{-1}\sum_{j=1}^{n}f_j\,g_{n-j}\quad(n\ge1)

と定める。右辺に現れるのはg0,…,gn−1g_0,\dots,g_{n-1}だけであるから、この式はnnについての強い帰納法でgng_nを一意に定める。G=∑n≥0gnxnG=\sum_{n\ge0}g_nx^{n}と置くと、n≥1n\ge1のとき

[xn](FG)=∑j=0nfjgn−j=f0gn+∑j=1nfjgn−j=0[x^{n}](FG)=\sum_{j=0}^{n}f_jg_{n-j}=f_0g_n+\sum_{j=1}^{n}f_jg_{n-j}=0

であり、[x0](FG)=f0g0=1[x^{0}](FG)=f_0g_0=1である。ゆえにFG=1FG=1である。

一意性。FG1=FG2=1FG_1=FG_2=1ならばG1=G1(FG2)=(G1F)G2=G2G_1=G_1(FG_2)=(G_1F)G_2=G_2である。▨

2 形式的 Laurent 級数と留数

係数公式の証明では、G−nG^{-n}のように負のべきをもつ級数を扱う。そこで有限個の負べきを許した級数の環を導入する。

定義 2.1. 写像F ⁣:Z→QF\colon\mathbb Z\to\mathbb Qであって、F(n)≠0F(n)\ne0を満たすn∈Zn\in\mathbb Zの全体が下に有界であるものを形式的 Laurent 級数 (formal Laurent series) とよび、F(n)F(n)を[xn]F[x^{n}]Fと書いてF=∑n∈Z([xn]F)xnF=\sum_{n\in\mathbb Z}([x^{n}]F)x^{n}と表す。形式的 Laurent 級数の全体をQ((x))\mathbb Q((x))と書く。和と積を

[xn](F+G)=[xn]F+[xn]G,[xn](FG)=∑i+j=n([xi]F)([xj]G)[x^{n}](F+G)=[x^{n}]F+[x^{n}]G,\qquad [x^{n}](FG)=\sum_{i+j=n}\bigl([x^{i}]F\bigr)\bigl([x^{j}]G\bigr)

で定める。積の右辺は、[xi]F≠0[x^{i}]F\ne0となるiiと[xj]G≠0[x^{j}]G\ne0となるjjがいずれも下に有界であることから、有限和である。位数ord⁡(F)\operatorname{ord}(F)を、F≠0F\ne0のとき[xn]F≠0[x^{n}]F\ne0を満たす最小の整数nn、F=0F=0のとき∞\inftyと定める。ord⁡(F)≥0\operatorname{ord}(F)\ge0を満たす元の全体がQ[[x]]\mathbb Q[[x]]である。

命題 2.2.Q((x))\mathbb Q((x))は上の演算について単位元11をもつ可換環であり、Q[[x]]\mathbb Q[[x]]をその部分環として含む。さらに次が成り立つ。

  1. F,G∈Q((x))F,G\in\mathbb Q((x))に対しord⁡(FG)=ord⁡(F)+ord⁡(G)\operatorname{ord}(FG)=\operatorname{ord}(F)+\operatorname{ord}(G)である。
  2. F≠0F\ne0ならばFFはQ((x))\mathbb Q((x))の可逆元である。とくにord⁡(F)=d\operatorname{ord}(F)=dならばord⁡(F−1)=−d\operatorname{ord}(F^{-1})=-dであり、任意の整数nnに対しord⁡(Fn)=nd\operatorname{ord}(F^{n})=ndである。

証明. 演算が閉じていること。和については定義から明らかである。積については、ord⁡(F)≥p\operatorname{ord}(F)\ge p、ord⁡(G)≥q\operatorname{ord}(G)\ge qならば[xn](FG)[x^{n}](FG)の定義に現れる和はi≥pi\ge pかつj≥qj\ge qの項に限られ、n<p+qn<p+qのとき空和すなわち00である。ゆえにFGFGの非零係数の添字も下に有界であり、Q((x))\mathbb Q((x))は積について閉じている。

加法群、可換性、分配法則、単位元。和は係数ごとに定義されているので、(Q((x)),+)(\mathbb Q((x)),+)は可換群である。可換性は、i+j=ni+j=nを満たす整数の対(i,j)(i,j)を(j,i)(j,i)へ写す全単射とQ\mathbb Qの積の可換性から従う。分配法則は、Q\mathbb Qの分配法則を各係数の有限和へ適用すれば従う。11を[x0]=1[x^{0}]=1かつ他の係数が00である元とすると[xn](F⋅1)=[xn]F[x^{n}](F\cdot1)=[x^{n}]Fであるから、11は単位元である。

結合性。結合性だけは、係数の三重和を直接に扱うかわりに§E13.1 命題 1.2へ帰着させる。整数kkとF∈Q((x))F\in\mathbb Q((x))に対し、[xn]σk(F)=[xn−k]F[x^{n}]\sigma_k(F)=[x^{n-k}]Fによってσk(F)\sigma_k(F)を定める。非零係数の添字は下に有界のままであるからσk(F)∈Q((x))\sigma_k(F)\in\mathbb Q((x))であり、σk\sigma_kはσ−k\sigma_{-k}を逆写像とする全単射で、σk∘σl=σk+l\sigma_k\circ\sigma_l=\sigma_{k+l}を満たす。積との関係は

[xn](σk(F) G)=∑i+j=n([xi−k]F)([xj]G)=∑i′+j=n−k([xi′]F)([xj]G)=[xn−k](FG)=[xn]σk(FG)[x^{n}]\bigl(\sigma_k(F)\,G\bigr)=\sum_{i+j=n}\bigl([x^{i-k}]F\bigr)\bigl([x^{j}]G\bigr) =\sum_{i'+j=n-k}\bigl([x^{i'}]F\bigr)\bigl([x^{j}]G\bigr)=[x^{n-k}](FG)=[x^{n}]\sigma_k(FG)

であり（i′=i−ki'=i-kと置き換えた）、σk(F)G=σk(FG)\sigma_k(F)G=\sigma_k(FG)である。可換性と合わせると、任意の整数a,ba,bとP,Q∈Q((x))P,Q\in\mathbb Q((x))に対し

σa+b(PQ)=σa(σb(PQ))=σa(P σb(Q))=σa(P) σb(Q)\sigma_{a+b}(PQ)=\sigma_a\bigl(\sigma_b(PQ)\bigr)=\sigma_a\bigl(P\,\sigma_b(Q)\bigr)=\sigma_a(P)\,\sigma_b(Q)

が成り立つ。

F,G,H∈Q((x))F,G,H\in\mathbb Q((x))を取る。非零係数の添字が下に有界であるから、A=σd(F)A=\sigma_d(F)、B=σd(G)B=\sigma_d(G)、C=σd(H)C=\sigma_d(H)がいずれもQ[[x]]\mathbb Q[[x]]に属する整数d≥0d\ge0が存在する。上の等式を二度用いると

σ3d((FG)H)=σ2d(FG) σd(H)=(σd(F) σd(G))σd(H)=(AB)C\sigma_{3d}\bigl((FG)H\bigr)=\sigma_{2d}(FG)\,\sigma_d(H)=\bigl(\sigma_d(F)\,\sigma_d(G)\bigr)\sigma_d(H)=(AB)C

であり、同様に

σ3d(F(GH))=σd(F) σ2d(GH)=σd(F)(σd(G) σd(H))=A(BC)\sigma_{3d}\bigl(F(GH)\bigr)=\sigma_d(F)\,\sigma_{2d}(GH)=\sigma_d(F)\bigl(\sigma_d(G)\,\sigma_d(H)\bigr)=A(BC)

である。Q[[x]]\mathbb Q[[x]]の元については、[xn](AB)[x^{n}](AB)の定義に現れる和のうち添字が負である項の係数が00であるから、Q((x))\mathbb Q((x))の積は Cauchy 積に一致する。ゆえに§E13.1 命題 1.2 (3)により(AB)C=A(BC)(AB)C=A(BC)である。σ3d\sigma_{3d}は全単射であるから(FG)H=F(GH)(FG)H=F(GH)である。

以上によりQ((x))\mathbb Q((x))は単位元をもつ可換環であり、ord⁡(F)≥0\operatorname{ord}(F)\ge0を満たす元の全体Q[[x]]\mathbb Q[[x]]は同じ演算と同じ単位元をもつ部分環である。

1 を示す。F=0F=0またはG=0G=0のときは両辺とも∞\inftyである。F,G≠0F,G\ne0とし、p=ord⁡(F)p=\operatorname{ord}(F)、q=ord⁡(G)q=\operatorname{ord}(G)と置く。F0=x−pFF_0=x^{-p}F、G0=x−qGG_0=x^{-q}Gと定めるとF0,G0∈Q[[x]]F_0,G_0\in\mathbb Q[[x]]であり、いずれも位数00である。FG=xp+qF0G0FG=x^{p+q}F_0G_0であり、§E13.2 補題 2.2によりord⁡(F0G0)=0\operatorname{ord}(F_0G_0)=0であるからord⁡(FG)=p+q\operatorname{ord}(FG)=p+qである。

2 を示す。F≠0F\ne0、d=ord⁡(F)d=\operatorname{ord}(F)とし、F0=x−dF∈Q[[x]]F_0=x^{-d}F\in\mathbb Q[[x]]と置く。[x0]F0≠0[x^{0}]F_0\ne0であるから定理 1.1によりF0F_0はQ[[x]]\mathbb Q[[x]]の可逆元であり、F−1=x−dF0−1F^{-1}=x^{-d}F_0^{-1}がFFの逆元である。1 によりord⁡(F−1)=−d\operatorname{ord}(F^{-1})=-dであり、n≥0n\ge0については 1 の繰り返しによりord⁡(Fn)=nd\operatorname{ord}(F^{n})=nd、n<0n<0についてはFn=(F−1)−nF^{n}=(F^{-1})^{-n}から同じ結論を得る。▨

定義 2.3.Q((x))\mathbb Q((x))の族(Fi)i∈I(F_i)_{i\in I}が総和可能 (summable) であるとは、各整数mmに対して{i∈I:ord⁡(Fi)≤m}\{i\in I:\operatorname{ord}(F_i)\le m\}が有限集合であることをいう。このとき

[xm]∑i∈IFi=∑ord⁡(Fi)≤m[xm]Fi[x^{m}]\sum_{i\in I}F_i=\sum_{\operatorname{ord}(F_i)\le m}[x^{m}]F_i

と定める。非零係数の添字は下に有界であるから、この式はQ((x))\mathbb Q((x))の元を定める。族の各項がQ[[x]]\mathbb Q[[x]]に属する場合、この定義は§E13.2 定義 2.3に一致する。F∈Q((x))F\in\mathbb Q((x))に対しres⁡(F)=[x−1]F\operatorname{res}(F)=[x^{-1}]Fと定め、FFの留数 (formal residue) とよぶ。

総和可能な族については、次の二つの性質を用いる。

補題 2.4.(Fi)i∈I(F_i)_{i\in I}をQ((x))\mathbb Q((x))の総和可能な族、S=∑i∈IFiS=\sum_{i\in I}F_iとする。

  1. 有限部分集合J⊆IJ\subseteq Iが{i:ord⁡(Fi)≤m}\{i:\operatorname{ord}(F_i)\le m\}を含むならば、ord⁡(S−∑i∈JFi)>m\operatorname{ord}\bigl(S-\sum_{i\in J}F_i\bigr)>mである。
  2. H∈Q((x))H\in\mathbb Q((x))とすると(HFi)i∈I(HF_i)_{i\in I}は総和可能でありHS=∑i∈IHFiHS=\sum_{i\in I}HF_iである。
  3. res⁡(S)=∑i∈Ires⁡(Fi)\operatorname{res}(S)=\sum_{i\in I}\operatorname{res}(F_i)である。右辺は有限個の項を除いて00である。

証明. 1 を示す。m′≤mm'\le mとすると、{i:ord⁡(Fi)≤m′}⊆J\{i:\operatorname{ord}(F_i)\le m'\}\subseteq Jであるから

[xm′]S=∑ord⁡(Fi)≤m′[xm′]Fi=∑i∈J[xm′]Fi[x^{m'}]S=\sum_{\operatorname{ord}(F_i)\le m'}[x^{m'}]F_i=\sum_{i\in J}[x^{m'}]F_i

である。最後の等号では、i∈Ji\in Jかつord⁡(Fi)>m′\operatorname{ord}(F_i)>m'の項が00であることを用いた。ゆえにS−∑i∈JFiS-\sum_{i\in J}F_iの第m′m'係数はm′≤mm'\le mのときすべて00である。

2 を示す。h=ord⁡(H)h=\operatorname{ord}(H)と置く。H=0H=0のときは両辺とも00である。H≠0H\ne0のとき命題 2.2 (1)によりord⁡(HFi)=h+ord⁡(Fi)\operatorname{ord}(HF_i)=h+\operatorname{ord}(F_i)であるから、{i:ord⁡(HFi)≤m}={i:ord⁡(Fi)≤m−h}\{i:\operatorname{ord}(HF_i)\le m\}=\{i:\operatorname{ord}(F_i)\le m-h\}は有限集合であり、族は総和可能である。mmを固定し、JJを{i:ord⁡(Fi)≤m−h}\{i:\operatorname{ord}(F_i)\le m-h\}を含む有限部分集合とする。1 によりord⁡(S−∑i∈JFi)>m−h\operatorname{ord}\bigl(S-\sum_{i\in J}F_i\bigr)>m-hであるから、ふたたび命題 2.2 (1)によりord⁡(HS−∑i∈JHFi)>m\operatorname{ord}\bigl(HS-\sum_{i\in J}HF_i\bigr)>mである。ゆえに

[xm](HS)=∑i∈J[xm](HFi)=[xm]∑i∈IHFi[x^{m}](HS)=\sum_{i\in J}[x^{m}](HF_i)=[x^{m}]\sum_{i\in I}HF_i

である。mmは任意であったから主張を得る。

3 はm=−1m=-1とした定義そのものである。ord⁡(Fi)>−1\operatorname{ord}(F_i)>-1を満たすiiについてはres⁡(Fi)=0\operatorname{res}(F_i)=0であり、ord⁡(Fi)≤−1\operatorname{ord}(F_i)\le-1を満たすiiは有限個である。▨

3 合成と形式微分

定義 3.1.G∈Q[[x]]G\in\mathbb Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとする。すなわち[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0である。F∈Q((x))F\in\mathbb Q((x))に対し、族(([xn]F) Gn)n∈Z\bigl(([x^{n}]F)\,G^{n}\bigr)_{n\in\mathbb Z}は総和可能である。実際、命題 2.2 (2)によりord⁡(Gn)=n\operatorname{ord}(G^{n})=nであり、[xn]F≠0[x^{n}]F\ne0となるnnは下に有界であるから、各mmに対して位数がmm以下である項は有限個である。そこで

F∘G=∑n∈Z([xn]F)GnF\circ G=\sum_{n\in\mathbb Z}\bigl([x^{n}]F\bigr)G^{n}

と定め、FFとGGの合成 (formal composition) とよぶ。F∈Q[[x]]F\in\mathbb Q[[x]]のときF∘G∈Q[[x]]F\circ G\in\mathbb Q[[x]]である。

補題 3.2.G∈Q[[x]]G\in\mathbb Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとする。

  1. x∘G=Gx\circ G=Gである。
  2. 任意のF∈Q((x))F\in\mathbb Q((x))に対しF∘x=FF\circ x=Fである。
  3. 任意のF∈Q((x))F\in\mathbb Q((x))に対しord⁡(F∘G)≥ord⁡(F)\operatorname{ord}(F\circ G)\ge\operatorname{ord}(F)である。

証明. 1 を示す。xxは[x1]=1[x^{1}]=1かつ他の係数が00である元であるから、定義 3.1の和はn=1n=1の項だけが残り、x∘G=G1=Gx\circ G=G^{1}=Gである。

2 を示す。ord⁡(x)=1\operatorname{ord}(x)=1であるからF∘xF\circ xが定まる。整数nnに対し[xm]xn[x^{m}]x^{n}はm=nm=nのとき11、それ以外のとき00である。ゆえにF∘x=∑n([xn]F)xnF\circ x=\sum_{n}([x^{n}]F)x^{n}の第mm係数は[xm]F[x^{m}]Fに等しく、F∘x=FF\circ x=Fである。

3 を示す。F=0F=0のときは両辺とも∞\inftyである。F≠0F\ne0としp=ord⁡(F)p=\operatorname{ord}(F)と置く。命題 2.2 (2)によりord⁡(Gn)=n\operatorname{ord}(G^{n})=nであるから、[xn]F≠0[x^{n}]F\ne0を満たす各nnについてord⁡(([xn]F)Gn)=n\operatorname{ord}\bigl(([x^{n}]F)G^{n}\bigr)=nであり、そのようなnnはすべてpp以上である。定義 2.3により、m<pm<pに対するF∘GF\circ Gの第mm係数は位数がmm以下の項だけの和であるが、そのような項は存在しない。ゆえにm<pm<pに対し[xm](F∘G)=0[x^{m}](F\circ G)=0であり、ord⁡(F∘G)≥p\operatorname{ord}(F\circ G)\ge pである。▨

命題 3.3.ord⁡(G)=1\operatorname{ord}(G)=1とする。F,F′∈Q((x))F,F'\in\mathbb Q((x))に対し

(F+F′)∘G=F∘G+F′∘G,(FF′)∘G=(F∘G)(F′∘G)(F+F')\circ G=F\circ G+F'\circ G,\qquad (FF')\circ G=(F\circ G)(F'\circ G)

が成り立つ。とくにF≠0F\ne0のとき(F−1)∘G=(F∘G)−1(F^{-1})\circ G=(F\circ G)^{-1}であり、任意の整数nnに対し(Fn)∘G=(F∘G)n(F^{n})\circ G=(F\circ G)^{n}である。

証明. 和については、係数ごとの定義から直ちに従う。

積を示す。F=0F=0またはF′=0F'=0のときは両辺とも00であるから、以下F≠0F\ne0かつF′≠0F'\ne0とする。mmを固定し、p=ord⁡(F)p=\operatorname{ord}(F)、p′=ord⁡(F′)p'=\operatorname{ord}(F')と置く。整数MMを、M≥mM\ge mかつM+1+min⁡(p,p′)>mM+1+\min(p,p')>mを満たすように取る。

P=∑n≤M([xn]F)xn,P′=∑n≤M([xn]F′)xnP=\sum_{n\le M}\bigl([x^{n}]F\bigr)x^{n},\qquad P'=\sum_{n\le M}\bigl([x^{n}]F'\bigr)x^{n}

と置くと、PPとP′P'は有限個の項からなる元であり、A=F−PA=F-P、A′=F′−P′A'=F'-P'はord⁡(A)>M\operatorname{ord}(A)>M、ord⁡(A′)>M\operatorname{ord}(A')>Mを満たす。

有限個の項からなる元については、命題 2.2の分配法則とGaGb=Ga+bG^{a}G^{b}=G^{a+b}により(PP′)∘G=(P∘G)(P′∘G)(PP')\circ G=(P\circ G)(P'\circ G)が成り立つ。

FF′−PP′=PA′+AP′+AA′FF'-PP'=PA'+AP'+AA'であり、命題 2.2 (1)により各項の位数はM+1+min⁡(p,p′)M+1+\min(p,p')以上である。したがってord⁡(FF′−PP′)>m\operatorname{ord}(FF'-PP')>mであり、補題 3.2 (3)によりord⁡((FF′−PP′)∘G)>m\operatorname{ord}\bigl((FF'-PP')\circ G\bigr)>mである。ゆえに[xm]((FF′)∘G)=[xm]((PP′)∘G)[x^{m}]\bigl((FF')\circ G\bigr)=[x^{m}]\bigl((PP')\circ G\bigr)である。

同様に、ord⁡(A∘G)>M\operatorname{ord}(A\circ G)>M、ord⁡(A′∘G)>M\operatorname{ord}(A'\circ G)>Mであり、ord⁡(F∘G)≥p\operatorname{ord}(F\circ G)\ge p、ord⁡(F′∘G)≥p′\operatorname{ord}(F'\circ G)\ge p'であるから

(F∘G)(F′∘G)−(P∘G)(P′∘G)=(P∘G)(A′∘G)+(A∘G)(P′∘G)+(A∘G)(A′∘G)(F\circ G)(F'\circ G)-(P\circ G)(P'\circ G)=(P\circ G)(A'\circ G)+(A\circ G)(P'\circ G)+(A\circ G)(A'\circ G)

の位数もM+1+min⁡(p,p′)>mM+1+\min(p,p')>mより大きい。ゆえに[xm]((F∘G)(F′∘G))=[xm]((P∘G)(P′∘G))[x^{m}]\bigl((F\circ G)(F'\circ G)\bigr)=[x^{m}]\bigl((P\circ G)(P'\circ G)\bigr)である。三つの等式を合わせて[xm]((FF′)∘G)=[xm]((F∘G)(F′∘G))[x^{m}]\bigl((FF')\circ G\bigr)=[x^{m}]\bigl((F\circ G)(F'\circ G)\bigr)を得る。mmは任意であった。

最後の主張は、1∘G=11\circ G=1と積の保存から(F−1∘G)(F∘G)=1(F^{-1}\circ G)(F\circ G)=1が従うことによる。整数べきについては、n≥0n\ge0では積の保存の繰り返し、n<0n<0ではFn=(F−1)−nF^{n}=(F^{-1})^{-n}による。▨

命題 3.4.G,H∈Q[[x]]G,H\in\mathbb Q[[x]]がord⁡(G)=ord⁡(H)=1\operatorname{ord}(G)=\operatorname{ord}(H)=1を満たすとする。このときord⁡(G∘H)=1\operatorname{ord}(G\circ H)=1であり、任意のF∈Q((x))F\in\mathbb Q((x))に対し

(F∘G)∘H=F∘(G∘H)(F\circ G)\circ H=F\circ(G\circ H)

が成り立つ。

証明.G∘H=∑n≥1([xn]G)HnG\circ H=\sum_{n\ge1}([x^{n}]G)H^{n}であり、ord⁡(Hn)=n\operatorname{ord}(H^{n})=nであるから[x1](G∘H)=([x1]G)([x1]H)≠0[x^{1}](G\circ H)=([x^{1}]G)([x^{1}]H)\ne0かつ[x0](G∘H)=0[x^{0}](G\circ H)=0である。ゆえにord⁡(G∘H)=1\operatorname{ord}(G\circ H)=1である。

有限個の項からなるP=∑n≤MpnxnP=\sum_{n\le M}p_nx^{n}については、命題 3.3によりGn∘H=(G∘H)nG^{n}\circ H=(G\circ H)^{n}であるから

(P∘G)∘H=∑n≤Mpn (Gn∘H)=∑n≤Mpn(G∘H)n=P∘(G∘H)(P\circ G)\circ H=\sum_{n\le M}p_n\,(G^{n}\circ H)=\sum_{n\le M}p_n(G\circ H)^{n}=P\circ(G\circ H)

である（有限和と合成の交換は命題 3.3の和の保存による）。

一般のFFについては、mmを固定しM≥mM\ge mを取ってF=P+AF=P+A（PPはMM次以下の項、ord⁡(A)>M\operatorname{ord}(A)>M）と分ける。補題 3.2 (3)を二度用いるとord⁡((A∘G)∘H)>M≥m\operatorname{ord}\bigl((A\circ G)\circ H\bigr)>M\ge mかつord⁡(A∘(G∘H))>M≥m\operatorname{ord}\bigl(A\circ(G\circ H)\bigr)>M\ge mである。ゆえに両辺の第mm係数はPPの分だけで決まり、上の等式から一致する。▨

定義 3.5.F∈Q((x))F\in\mathbb Q((x))に対し、[xn]F′=(n+1)[xn+1]F[x^{n}]F'=(n+1)[x^{n+1}]F（n∈Zn\in\mathbb Z）で定まるF′∈Q((x))F'\in\mathbb Q((x))をFFの形式微分 (formal derivative) とよぶ。すなわちF=∑nfnxnF=\sum_n f_nx^{n}のときF′=∑nnfnxn−1F'=\sum_n nf_nx^{n-1}である。

命題 3.6.F,G∈Q((x))F,G\in\mathbb Q((x))、λ∈Q\lambda\in\mathbb Qに対し次が成り立つ。

  1. (F+G)′=F′+G′(F+G)'=F'+G'および(λF)′=λF′(\lambda F)'=\lambda F'。
  2. (FG)′=F′G+FG′(FG)'=F'G+FG'。
  3. 総和可能な族(Fi)i∈I(F_i)_{i\in I}に対し(Fi′)i∈I(F_i')_{i\in I}は総和可能であり(∑iFi)′=∑iFi′\bigl(\sum_iF_i\bigr)'=\sum_iF_i'。
  4. F≠0F\ne0と整数nnに対し(Fn)′=nFn−1F′(F^{n})'=nF^{n-1}F'。

証明. 1 は係数ごとの定義から直ちに従う。

2 を示す。fi=[xi]Ff_i=[x^{i}]F、gj=[xj]Gg_j=[x^{j}]Gと書く。定義により

[xm]((FG)′)=(m+1)[xm+1](FG)=(m+1)∑i+j=m+1figj[x^{m}]\bigl((FG)'\bigr)=(m+1)[x^{m+1}](FG)=(m+1)\sum_{i+j=m+1}f_ig_j

である。他方

[xm](F′G+FG′)=∑i+j=m(i+1)fi+1gj+∑i+j=mfi(j+1)gj+1[x^{m}](F'G+FG')=\sum_{i+j=m}(i+1)f_{i+1}g_j+\sum_{i+j=m}f_i(j+1)g_{j+1}

であり、第一の和でi′=i+1i'=i+1、第二の和でj′=j+1j'=j+1と置き換えると、いずれもi+j=m+1i+j=m+1を満たす対にわたる和になり、

∑i+j=m+1i figj+∑i+j=m+1j figj=∑i+j=m+1(i+j)figj=(m+1)∑i+j=m+1figj\sum_{i+j=m+1}i\,f_ig_j+\sum_{i+j=m+1}j\,f_ig_j=\sum_{i+j=m+1}(i+j)f_ig_j=(m+1)\sum_{i+j=m+1}f_ig_j

を得る。ゆえに 2 が成り立つ。

3 を示す。ord⁡(Fi′)≥ord⁡(Fi)−1\operatorname{ord}(F_i')\ge\operatorname{ord}(F_i)-1であるから、{i:ord⁡(Fi′)≤m}⊆{i:ord⁡(Fi)≤m+1}\{i:\operatorname{ord}(F_i')\le m\}\subseteq\{i:\operatorname{ord}(F_i)\le m+1\}は有限集合であり、族は総和可能である。係数については

[xm](∑iFi)′=(m+1)[xm+1]∑iFi=(m+1)∑ord⁡(Fi)≤m+1[xm+1]Fi=∑i[xm]Fi′[x^{m}]\Bigl(\sum_iF_i\Bigr)'=(m+1)[x^{m+1}]\sum_iF_i=(m+1)\sum_{\operatorname{ord}(F_i)\le m+1}[x^{m+1}]F_i=\sum_i[x^{m}]F_i'

である。

4 を示す。n≥0n\ge0のときは 2 を用いたnnについての帰納法による（n=0n=0のとき両辺とも00である）。n<0n<0のとき、FnF−n=1F^{n}F^{-n}=1の両辺を微分すると 2 により

(Fn)′F−n+Fn(F−n)′=0(F^{n})'F^{-n}+F^{n}(F^{-n})'=0

である。−n>0-n>0であるから(F−n)′=−nF−n−1F′(F^{-n})'=-nF^{-n-1}F'であり、これを代入してFnF^{n}を掛けると

(Fn)′=−Fn(F−n)′Fn=nFnF−n−1F′Fn=nFn−1F′(F^{n})'=-F^{n}(F^{-n})'F^{n}=nF^{n}F^{-n-1}F'F^{n}=nF^{n-1}F'

を得る。▨

命題 3.7 (連鎖律).G∈Q[[x]]G\in\mathbb Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとき、任意のF∈Q((x))F\in\mathbb Q((x))に対し

(F∘G)′=(F′∘G) G′(F\circ G)'=(F'\circ G)\,G'

が成り立つ。

証明.fn=[xn]Ff_n=[x^{n}]Fと書く。命題 3.6 (3)と合成の定義により

(F∘G)′=(∑nfnGn)′=∑nfn (Gn)′(F\circ G)'=\Bigl(\sum_{n}f_nG^{n}\Bigr)'=\sum_{n}f_n\,(G^{n})'

である。命題 3.6 (4)により(Gn)′=nGn−1G′(G^{n})'=nG^{n-1}G'であるから、補題 2.4 (2)をH=G′H=G'として用いて

(F∘G)′=∑nnfnGn−1 G′=(∑nnfnGn−1)G′(F\circ G)'=\sum_{n}nf_nG^{n-1}\,G'=\Bigl(\sum_{n}nf_nG^{n-1}\Bigr)G'

となる。F′=∑nnfnxn−1F'=\sum_n nf_nx^{n-1}であるから、括弧の中はF′∘GF'\circ Gにほかならない。▨

補題 3.8.F∈Q((x))F\in\mathbb Q((x))に対しres⁡(F′)=0\operatorname{res}(F')=0が成り立つ。

証明. 定義により[x−1]F′=(−1+1)[x0]F=0[x^{-1}]F'=(-1+1)[x^{0}]F=0である。▨

補題 3.9.G∈Q[[x]]G\in\mathbb Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとする。任意のF∈Q((x))F\in\mathbb Q((x))に対し

res⁡((F∘G) G′)=res⁡(F)\operatorname{res}\bigl((F\circ G)\,G'\bigr)=\operatorname{res}(F)

が成り立つ。

証明.fn=[xn]Ff_n=[x^{n}]Fと書く。補題 2.4 (2)により(F∘G)G′=∑nfnGnG′(F\circ G)G'=\sum_n f_nG^{n}G'であり、この族は総和可能である。補題 2.4 (3)により

res⁡((F∘G)G′)=∑nfnres⁡(GnG′)\operatorname{res}\bigl((F\circ G)G'\bigr)=\sum_{n}f_n\operatorname{res}\bigl(G^{n}G'\bigr)

である。右辺は有限個の項を除いて00である。したがって、各整数nnについてres⁡(GnG′)=res⁡(xn)\operatorname{res}(G^{n}G')=\operatorname{res}(x^{n})を示せばよい。

n≠−1n\ne-1のとき、命題 3.6 (4)によりGnG′=1n+1(Gn+1)′G^{n}G'=\frac{1}{n+1}\bigl(G^{n+1}\bigr)'であるから、補題 3.8によりres⁡(GnG′)=0\operatorname{res}(G^{n}G')=0である。他方res⁡(xn)=0\operatorname{res}(x^{n})=0である。

n=−1n=-1のとき、c=[x1]G≠0c=[x^{1}]G\ne0と置き、U=(cx)−1GU=(cx)^{-1}GとするとU∈Q[[x]]U\in\mathbb Q[[x]]かつ[x0]U=1[x^{0}]U=1である。G=cxUG=cxUであるから命題 3.6 (2)によりG′=cU+cxU′G'=cU+cxU'であり、

G−1G′=cU+cxU′cxU=1x+U′UG^{-1}G'=\frac{cU+cxU'}{cxU}=\frac1x+\frac{U'}{U}

である。定理 1.1によりUUはQ[[x]]\mathbb Q[[x]]の可逆元であり、U′∈Q[[x]]U'\in\mathbb Q[[x]]であるからU′/U∈Q[[x]]U'/U\in\mathbb Q[[x]]である。ゆえにその留数は00であり、res⁡(G−1G′)=1=res⁡(x−1)\operatorname{res}(G^{-1}G')=1=\operatorname{res}(x^{-1})である。▨

4 合成逆元

4.1 証明方針

GGを定数項が零で一次係数が零でない形式的冪級数とし、G∘Gˉ=xG\circ\bar G=xを満たすGˉ\bar Gを係数ごとに決めていく。Gˉ=∑n≥1bnxn\bar G=\sum_{n\ge1}b_nx^{n}と置くと

G∘Gˉ=∑k≥1gkGˉkG\circ\bar G=\sum_{k\ge1}g_k\bar G^{k}

であり、第nn係数を取るとg1bng_1b_nという項と、k≥2k\ge2からの寄与が現れる。ord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1であるから[xn]Gˉk[x^{n}]\bar G^{k}はb1,…,bn−k+1b_1,\dots,b_{n-k+1}だけで決まり、k≥2k\ge2ならば添字はn−1n-1以下である。したがって、第nn係数の方程式はbnb_nについて一次であり、g1≠0g_1\ne0によって一意に解くことができる。これで右合成逆元の存在と一意性が得られる。

両側であることは、いったん得たGˉ\bar Gにもう一度同じ構成を適用して得る。Gˉ\bar Gの一次係数は1/g11/g_1であって零でないから、Gˉ∘H=x\bar G\circ H=xを満たすHHが存在する。合成の結合性によりG=G∘(Gˉ∘H)=(G∘Gˉ)∘H=HG=G\circ(\bar G\circ H)=(G\circ\bar G)\circ H=Hとなり、Gˉ∘G=x\bar G\circ G=xが従う。

定理 4.1.G∈Q[[x]]G\in\mathbb Q[[x]]が[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0を満たすとする。このときord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1かつ

G∘Gˉ=xG\circ\bar G=x

を満たすGˉ∈Q[[x]]\bar G\in\mathbb Q[[x]]がただ一つ存在する。さらに、このGˉ\bar GはGˉ∘G=x\bar G\circ G=xも満たす。Gˉ\bar GをGGの合成逆元とよぶ。

証明.gk=[xk]Gg_k=[x^{k}]Gと書く。仮定はg0=0g_0=0、g1≠0g_1\ne0である。

右合成逆元の存在と一意性。Gˉ=∑n≥1bnxn\bar G=\sum_{n\ge1}b_nx^{n}の形の元を求める。ord⁡(Gˉ)≥1\operatorname{ord}(\bar G)\ge1であるからord⁡(Gˉk)≥k\operatorname{ord}(\bar G^{k})\ge kであり、

[xn](G∘Gˉ)=∑k=1ngk [xn]Gˉk[x^{n}](G\circ\bar G)=\sum_{k=1}^{n}g_k\,[x^{n}]\bar G^{k}

である。k≥2k\ge2のとき、[xn]Gˉk[x^{n}]\bar G^{k}はGˉ\bar Gの第11係数から第n−k+1n-k+1係数までだけで決まる。実際、[xn]Gˉk=∑bn1⋯bnk[x^{n}]\bar G^{k}=\sum b_{n_1}\cdots b_{n_k}（n1+⋯+nk=nn_1+\dots+n_k=n、各ni≥1n_i\ge1）であり、各nin_iはn−(k−1)≤n−1n-(k-1)\le n-1以下である。またk=1k=1の項はg1bng_1b_nである。したがって

[xn](G∘Gˉ)=g1bn+Φn(b1,…,bn−1)[x^{n}](G\circ\bar G)=g_1b_n+\Phi_n(b_1,\dots,b_{n-1})

の形に書くことができる。ここでΦn\Phi_nはb1,…,bn−1b_1,\dots,b_{n-1}とg1,…,gng_1,\dots,g_nから定まる有理数であり、n=1n=1のときΦ1=0\Phi_1=0である。

G∘Gˉ=xG\circ\bar G=xという条件は、n=1n=1でg1b1=1g_1b_1=1、n≥2n\ge2でg1bn+Φn(b1,…,bn−1)=0g_1b_n+\Phi_n(b_1,\dots,b_{n-1})=0と書くことができる。g1≠0g_1\ne0であるから、nnについての強い帰納法によってbnb_nが一意に定まる。とくにb1=1/g1≠0b_1=1/g_1\ne0であるからord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1である。

両側であること。Gˉ\bar Gは[x0]Gˉ=0[x^{0}]\bar G=0と[x1]Gˉ≠0[x^{1}]\bar G\ne0を満たすので、上の構成をGˉ\bar Gへ適用するとGˉ∘H=x\bar G\circ H=xを満たすH∈Q[[x]]H\in\mathbb Q[[x]]が存在し、ord⁡(H)=1\operatorname{ord}(H)=1である。命題 3.4と補題 3.2 (1)と 2 により

G=G∘x=G∘(Gˉ∘H)=(G∘Gˉ)∘H=x∘H=HG=G\circ x=G\circ(\bar G\circ H)=(G\circ\bar G)\circ H=x\circ H=H

である。ゆえにGˉ∘G=Gˉ∘H=x\bar G\circ G=\bar G\circ H=xである。▨

5 Lagrange–Bürmann の係数公式

5.1 証明方針

H∈Q((x))H\in\mathbb Q((x))を与え、F=H∘GˉF=H\circ\bar Gと置く。合成の結合性によりF∘G=H∘(Gˉ∘G)=HF\circ G=H\circ(\bar G\circ G)=Hであるから、HHはFFをGGで置き換えたものである。目標はFFの第nn係数をHHとGGだけで書くことである。

出発点は、FFの第nn係数がF′F'の第n−1n-1係数の1/n1/n倍であること、そしてこの係数が留数としてres⁡(F′x−n)\operatorname{res}(F'x^{-n})と書くことができることである。次に、この留数へ補題 3.9を逆向きに用いる。すなわちΨ=F′x−n\Psi=F'x^{-n}と置くとres⁡(Ψ)=res⁡((Ψ∘G)G′)\operatorname{res}(\Psi)=\operatorname{res}\bigl((\Psi\circ G)G'\bigr)である。

最後にΨ∘G\Psi\circ GをHHで書き直す。合成が環準同型であること（命題 3.3）からΨ∘G=(F′∘G) G−n\Psi\circ G=(F'\circ G)\,G^{-n}であり、連鎖律（命題 3.7）によりH′=(F∘G)′=(F′∘G)G′H'=(F\circ G)'=(F'\circ G)G'である。この二つを合わせると(Ψ∘G)G′=H′G−n(\Psi\circ G)G'=H'G^{-n}となり、求める等式を得る。

定理 5.1 (Lagrange–Bürmann の係数公式).G∈Q[[x]]G\in\mathbb Q[[x]]が[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0を満たすとし、Gˉ\bar Gをその合成逆元とする。任意のH∈Q((x))H\in\mathbb Q((x))と任意の整数n≠0n\ne0に対し

n [xn](H∘Gˉ)=res⁡(H′ G−n)n\,[x^{n}]\bigl(H\circ\bar G\bigr)=\operatorname{res}\bigl(H'\,G^{-n}\bigr)

が成り立つ。

証明.F=H∘GˉF=H\circ\bar Gと置く。命題 3.4と定理 4.1により

F∘G=(H∘Gˉ)∘G=H∘(Gˉ∘G)=H∘x=HF\circ G=(H\circ\bar G)\circ G=H\circ(\bar G\circ G)=H\circ x=H

である。最後の等号は補題 3.2 (2)による。

定義 3.5により[xn−1]F′=n[xn]F[x^{n-1}]F'=n[x^{n}]Fであり、これはres⁡(F′x−n)\operatorname{res}\bigl(F'x^{-n}\bigr)に等しい。Ψ=F′x−n\Psi=F'x^{-n}と置く。補題 3.9をΨ\Psiへ適用すると

n [xn]F=res⁡(Ψ)=res⁡((Ψ∘G) G′)n\,[x^{n}]F=\operatorname{res}(\Psi)=\operatorname{res}\bigl((\Psi\circ G)\,G'\bigr)

である。

Ψ∘G\Psi\circ Gを計算する。命題 3.3により、積の合成は合成の積であり、x−n∘G=G−nx^{-n}\circ G=G^{-n}であるから

Ψ∘G=(F′∘G) G−n\Psi\circ G=(F'\circ G)\,G^{-n}

である。他方、命題 3.7をFFとGGへ適用すると

H′=(F∘G)′=(F′∘G) G′H'=(F\circ G)'=(F'\circ G)\,G'

である。ゆえに

(Ψ∘G) G′=(F′∘G) G′ G−n=H′ G−n(\Psi\circ G)\,G'=(F'\circ G)\,G'\,G^{-n}=H'\,G^{-n}

であり、主張の等式を得る。▨

系 5.2.ϕ∈Q[[x]]\phi\in\mathbb Q[[x]]が[x0]ϕ≠0[x^{0}]\phi\ne0を満たすとする。このとき

W=x (ϕ∘W),ord⁡(W)=1W=x\,(\phi\circ W),\qquad \operatorname{ord}(W)=1

を満たすW∈Q[[x]]W\in\mathbb Q[[x]]がただ一つ存在する。さらに、任意のH∈Q[[x]]H\in\mathbb Q[[x]]と任意の整数n≥1n\ge1に対し

[xn](H∘W)=1n [xn−1](H′ ϕn)[x^{n}]\bigl(H\circ W\bigr)=\frac1n\,[x^{n-1}]\bigl(H'\,\phi^{n}\bigr)

が成り立つ。とくにH=xH=xと取ると

[xn]W=1n [xn−1]ϕn[x^{n}]W=\frac1n\,[x^{n-1}]\phi^{n}

である。

証明.定理 1.1によりϕ\phiはQ[[x]]\mathbb Q[[x]]の可逆元である。G=x ϕ−1G=x\,\phi^{-1}と置くと[x0]G=0[x^{0}]G=0かつ[x1]G=([x0]ϕ)−1≠0[x^{1}]G=([x^{0}]\phi)^{-1}\ne0であり、ord⁡(G)=1\operatorname{ord}(G)=1である。

ord⁡(W)=1\operatorname{ord}(W)=1を満たすW∈Q[[x]]W\in\mathbb Q[[x]]について、命題 3.3と補題 3.2 (1)により

G∘W=(x∘W) (ϕ−1∘W)=W (ϕ∘W)−1G\circ W=(x\circ W)\,\bigl(\phi^{-1}\circ W\bigr)=W\,(\phi\circ W)^{-1}

である。ゆえにG∘W=xG\circ W=xであることとW=x(ϕ∘W)W=x(\phi\circ W)であることは同値である。定理 4.1により、前者を満たすWWはただ一つ存在し、それはGˉ\bar Gである。

係数公式を示す。定理 5.1をHHとn≥1n\ge1へ適用すると

n [xn](H∘W)=res⁡(H′G−n)=res⁡(H′x−nϕn)=[xn−1](H′ϕn)n\,[x^{n}](H\circ W)=\operatorname{res}\bigl(H'G^{-n}\bigr)=\operatorname{res}\bigl(H'x^{-n}\phi^{n}\bigr)=[x^{n-1}]\bigl(H'\phi^{n}\bigr)

である。H=xH=xのときH′=1H'=1であるから最後の主張を得る。▨

6 Catalan 数と根付き平面木

定義 6.1.C0=1C_0=1とし、n≥0n\ge0に対し

Cn+1=∑i=0nCiCn−iC_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}

と定める。(Cn)n≥0(C_n)_{n\ge0}を Catalan 数 (Catalan numbers) とよび、その通常母関数をC(x)=∑n≥0CnxnC(x)=\sum_{n\ge0}C_nx^{n}と書く。

定理 6.2. すべての整数m≥0m\ge0に対し

Cm=1m+1(2mm)C_m=\frac{1}{m+1}\binom{2m}{m}

が成り立つ。

証明. まずC(x)=1+xC(x)2C(x)=1+xC(x)^{2}を示す。[x0][x^{0}]については、左辺がC0=1C_0=1、右辺が11である。n≥0n\ge0について[xn+1][x^{n+1}]を比べると、左辺はCn+1C_{n+1}であり、右辺は Cauchy 積により

[xn+1](xC2)=[xn]C2=∑i=0nCiCn−i[x^{n+1}]\bigl(xC^{2}\bigr)=[x^{n}]C^{2}=\sum_{i=0}^{n}C_iC_{n-i}

である。定義 6.1の漸化式により両者は等しい。

W=xC(x)W=xC(x)と置く。[x0]W=0[x^{0}]W=0かつ[x1]W=C0=1[x^{1}]W=C_0=1であるからord⁡(W)=1\operatorname{ord}(W)=1である。関数方程式C=1+xC2C=1+xC^{2}の両辺にxxを掛けると

W=x+x2C2=x+W2W=x+x^{2}C^{2}=x+W^{2}

となる。ゆえにW(1−W)=xW(1-W)=xである。ord⁡(W)≥1\operatorname{ord}(W)\ge1であるから[x0](1−W)=1≠0[x^{0}](1-W)=1\ne0であり、定理 1.1により1−W1-Wは可逆である。したがって

W=x (1−W)−1W=x\,(1-W)^{-1}

である。

ϕ(x)=(1−x)−1\phi(x)=(1-x)^{-1}と置くと[x0]ϕ=1≠0[x^{0}]\phi=1\ne0である。命題 3.3によりϕ∘W=((1−x)∘W)−1=(1−W)−1\phi\circ W=\bigl((1-x)\circ W\bigr)^{-1}=(1-W)^{-1}であるから、上の式はW=x(ϕ∘W)W=x(\phi\circ W)にほかならない。系 5.2により、n≥1n\ge1に対し

[xn]W=1n[xn−1]ϕn=1n[xn−1]1(1−x)n[x^{n}]W=\frac1n[x^{n-1}]\phi^{n}=\frac1n[x^{n-1}]\frac{1}{(1-x)^{n}}

である。§D2.4 命題 5.2をα=1\alpha=1、m=nm=nとして用いると

1(1−x)n=∑k≥0(k+n−1n−1)xk\frac{1}{(1-x)^{n}}=\sum_{k\ge0}\binom{k+n-1}{n-1}x^{k}

である。この等式はC[[x]]\mathbb C[[x]]において述べられているが、両辺の係数はすべて有理数であり、§E13.1 命題 1.2によりQ[[x]]\mathbb Q[[x]]はC[[x]]\mathbb C[[x]]の部分環であるから、Q[[x]]\mathbb Q[[x]]における等式として読んでよい。ゆえに[xn−1](1−x)−n=(2n−2n−1)[x^{n-1}](1-x)^{-n}=\binom{2n-2}{n-1}である。[xn]W=[xn−1]C=Cn−1[x^{n}]W=[x^{n-1}]C=C_{n-1}であるから

Cn−1=1n(2n−2n−1)C_{n-1}=\frac1n\binom{2n-2}{n-1}

となる。m=n−1m=n-1と置き直すと、m≥0m\ge0に対しCm=1m+1(2mm)C_m=\frac{1}{m+1}\binom{2m}{m}である。▨

例 6.3 (Catalan 数の検算).定義 6.1の漸化式から順に計算すると

C1=C0C0=1,C2=2C0C1=2,C3=2C0C2+C1C1=2⋅2+1=5,C4=2C0C3+2C1C2=2⋅5+2⋅2=14C_1=C_0C_0=1,\quad C_2=2C_0C_1=2,\quad C_3=2C_0C_2+C_1C_1=2\cdot2+1=5,\quad C_4=2C_0C_3+2C_1C_2=2\cdot5+2\cdot2=14

である。定理 6.2の式はm=0,1,2,3,4m=0,1,2,3,4に対して

11(00)=1,12(21)=1,13(42)=63=2,14(63)=204=5,15(84)=705=14\frac11\binom00=1,\quad \frac12\binom21=1,\quad \frac13\binom42=\frac63=2,\quad \frac14\binom63=\frac{20}4=5,\quad \frac15\binom84=\frac{70}5=14

を与え、すべて一致する。

反転公式の側からも確かめる。n=3n=3のとき[x3]W=13[x2](1−x)−3=13(2+22)=13⋅6=2[x^{3}]W=\frac13[x^{2}](1-x)^{-3}=\frac13\binom{2+2}{2}=\frac13\cdot6=2であり、[x3]W=C2=2[x^{3}]W=C_2=2と一致する。n=5n=5のとき[x5]W=15(84)=14[x^{5}]W=\frac15\binom84=14であり、C4=14C_4=14と一致する。

定義 6.4. 根付き平面木 (rooted plane tree) を、節点の個数についての再帰によって定める。整数k≥0k\ge0と根付き平面木の列(T1,…,Tk)(T_1,\dots,T_k)に対し、記号∙\bulletを根とする組

T=(∙,(T1,…,Tk))T=\bigl(\bullet,(T_1,\dots,T_k)\bigr)

を根付き平面木とし、その大きさ (size)（節点の個数）を∣T∣=1+∑i=1k∣Ti∣|T|=1+\sum_{i=1}^{k}|T_i|と定める。k=0k=0のときTTは根だけからなる木であり∣T∣=1|T|=1である。各TiT_iの大きさは∣T∣|T|より小さいので、この再帰は整礎である。大きさnnの根付き平面木の個数をtnt_nと書く。

定理 6.5.n≥1n\ge1に対しtnt_nは有限であり、

tn=1n(2n−2n−1)=Cn−1t_n=\frac1n\binom{2n-2}{n-1}=C_{n-1}

が成り立つ。

証明. まずtnt_nが有限であることをnnについての強い帰納法で示す。大きさnnの木T=(∙,(T1,…,Tk))T=(\bullet,(T_1,\dots,T_k))では∑i∣Ti∣=n−1\sum_i|T_i|=n-1であり、各∣Ti∣≥1|T_i|\ge1であるからk≤n−1k\le n-1である。kkと大きさの組(n1,…,nk)(n_1,\dots,n_k)を固定すると、木の個数は∏itni\prod_i t_{n_i}であり、各ni≤n−1n_i\le n-1であるから帰納法の仮定により有限である。組の個数も有限であるからtnt_nは有限である。同時に、加法原理（§D2.2 定理 2.1）と乗法原理（§D2.2 定理 2.3）により

tn=∑k=0n−1 ∑n1,…,nk≥1n1+⋯+nk=n−1 ∏i=1ktnit_n=\sum_{k=0}^{n-1}\ \sum_{\substack{n_1,\dots,n_k\ge1\\ n_1+\dots+n_k=n-1}}\ \prod_{i=1}^{k}t_{n_i}

が成り立つ（k=0k=0の項は、n=1n=1のとき11、n≥2n\ge2のとき00と読む）。

T(x)=∑n≥1tnxnT(x)=\sum_{n\ge1}t_nx^{n}と置く。ord⁡(T)≥1\operatorname{ord}(T)\ge1であるから命題 2.2 (1)によりord⁡(Tk)≥k\operatorname{ord}(T^{k})\ge kであり、族(Tk)k≥0(T^{k})_{k\ge0}は総和可能である。S=∑k≥0TkS=\sum_{k\ge0}T^{k}と置く。補題 2.4 (2)によりTS=∑k≥0Tk+1TS=\sum_{k\ge0}T^{k+1}である。各m≥0m\ge0について、位数の評価から

[xm]S=∑k=0m[xm]Tk,[xm](TS)=∑k=1m[xm]Tk[x^{m}]S=\sum_{k=0}^{m}[x^{m}]T^{k},\qquad [x^{m}](TS)=\sum_{k=1}^{m}[x^{m}]T^{k}

であるから（m=0m=0のとき第二式の和は空である）、[xm](S−TS)=[xm]T0=[xm]1[x^{m}](S-TS)=[x^{m}]T^{0}=[x^{m}]1である。ゆえに(1−T)S=1(1-T)S=1であり、定理 1.1によりS=(1−T)−1S=(1-T)^{-1}である。

§E13.2 補題 2.6をkk個の因子TTへ適用すると

[xn−1]Tk=∑n1,…,nk≥0n1+⋯+nk=n−1∏i=1ktni[x^{n-1}]T^{k}=\sum_{\substack{n_1,\dots,n_k\ge0\\ n_1+\dots+n_k=n-1}}\prod_{i=1}^{k}t_{n_i}

であり、t0=0t_0=0と読めばni≥1n_i\ge1の項だけが残る。また[xn−1]Tk=0[x^{n-1}]T^{k}=0（k>n−1k>n-1）である。ゆえに上の数え上げの等式は

[xn](xS)=[xn−1]S=∑k=0n−1[xn−1]Tk=tn=[xn]T[x^{n}]\bigl(xS\bigr)=[x^{n-1}]S=\sum_{k=0}^{n-1}[x^{n-1}]T^{k}=t_n=[x^{n}]T

と書き換えられる。[x0](xS)=0=[x0]T[x^{0}](xS)=0=[x^{0}]TであるからT=xS=x(1−T)−1T=xS=x(1-T)^{-1}である。

ϕ(x)=(1−x)−1\phi(x)=(1-x)^{-1}と置く。定理 6.2の証明と同じくϕ∘T=(1−T)−1\phi\circ T=(1-T)^{-1}であるから、TTはT=x(ϕ∘T)T=x(\phi\circ T)とord⁡(T)=1\operatorname{ord}(T)=1を満たす。[x1]T=t1=1≠0[x^{1}]T=t_1=1\ne0であることは、大きさ11の木が根だけからなる木ただ一つであることによる。系 5.2の一意性によりTTは定理 6.2の証明に現れたWWに等しく、

tn=[xn]T=1n(2n−2n−1)=Cn−1t_n=[x^{n}]T=\frac1n\binom{2n-2}{n-1}=C_{n-1}

である。▨

例 6.6 (小さい根付き平面木の個数).n=1,2,3,4n=1,2,3,4について定理 6.5を直接の数え上げで確かめる。

n=1n=1では、根だけからなる木ただ一つでありt1=1t_1=1である。n=2n=2では、根に大きさ11の子が一つ付く木だけでありt2=1t_2=1である。n=3n=3では、根に大きさ11の子が二つ付く木と、根に大きさ22の子が一つ付く木の二つでありt3=2t_3=2である。n=4n=4では、根の子の列の大きさの組が(1,1,1)(1,1,1)、(1,2)(1,2)、(2,1)(2,1)、(3)(3)の四通りであり、それぞれ木の個数はt13=1t_1^{3}=1、t1t2=1t_1t_2=1、t2t1=1t_2t_1=1、t3=2t_3=2であるからt4=1+1+1+2=5t_4=1+1+1+2=5である。

公式はt1=11(00)=1t_1=\frac11\binom00=1、t2=12(21)=1t_2=\frac12\binom21=1、t3=13(42)=2t_3=\frac13\binom42=2、t4=14(63)=5t_4=\frac14\binom63=5を与え、すべて一致する。

7 演習

問題 7.1.

  1. 定理 4.1の証明のうち、右合成逆元の係数bnb_nが一意に定まる段階を再現せよ。とくに、k≥2k\ge2のとき[xn]Gˉk[x^{n}]\bar G^{k}にbnb_nが現れない理由を、ord⁡(Gˉ)≥1\operatorname{ord}(\bar G)\ge1から書き下せ。
  2. 定理 4.1の証明では、両側であることを示すために合成の結合性を用いた。[x1]G=0[x^{1}]G=0を許すと、右合成逆元の構成のどの段階が破れるかを述べよ。さらにG=x2G=x^{2}に対してG∘Gˉ=xG\circ\bar G=xを満たすGˉ∈Q[[x]]\bar G\in\mathbb Q[[x]]が存在しないことを証明せよ。
  3. 補題 3.9の証明で、n=−1n=-1の場合を他のnnと分けて扱った。n≠−1n\ne-1の議論をn=−1n=-1へそのまま適用しようとするとどこで破れるかを述べ、G=x+x2G=x+x^{2}についてres⁡(G−1G′)=1\operatorname{res}(G^{-1}G')=1を直接の計算で確かめよ。
  4. 定理 5.1の証明を、F=H∘GˉF=H\circ\bar Gと置くところから再現せよ。補題 3.9をどちらの向きに用いたかを明示せよ。
  5. 系 5.2をϕ(x)=1+x\phi(x)=1+xとして適用し、W=x(1+W)W=x(1+W)を満たすWWの係数を公式から求めよ。さらに、同じ関数方程式を直接に解いて得られる式と一致することを確かめよ。
  6. 系 5.2をH(x)=x2H(x)=x^{2}、ϕ(x)=(1−x)−1\phi(x)=(1-x)^{-1}として適用し、[xn]W2[x^{n}]W^{2}を二項係数で表せ。n=4n=4の場合に例 6.3の値から直接に計算した[x4]W2[x^{4}]W^{2}と一致することを確かめよ。

8 扱った範囲と次の記事

有理数体上の形式的冪級数の可逆元、形式的 Laurent 級数、合成、形式微分、連鎖律および留数を定義し、留数の変数変換を証明した。これらを用いて、定数項が零で一次係数が零でない級数の合成逆元が一意に存在することと、Lagrange–Bürmann の係数公式を証明した。応用として、漸化式で定めた Catalan 数の閉じた式と、根付き平面木の個数を同じ関数方程式から導いた。

多変数の反転公式、係数の解析的な漸近評価、および形式的冪級数の代数的・微分方程式的な性質は扱っていない。次の記事では、平面に描くことのできるグラフの頂点彩色へ移り、Kempe 鎖と色交換によって五色定理を扱う。

参考文献

  1. Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.Lagrange–Bürmann の係数公式と根付き平面木への適用を参考にした。
  2. Ivan Niven, Formal power series, The American Mathematical Monthly 76 (1969), no. 8, 871–889.形式的冪級数の合成、形式微分および可逆性を収束と無関係に扱う枠組みを参考にした。
  3. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.形式的冪級数の代数的な取り扱いと単純生成木の関数方程式を参考にした。

前提記事