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

定理 1.1.F∈Q[[x]]F\in\Q[[x]]がQ[[x]]\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\Z\to\Qであって、F(n)≠0F(n)\ne0を満たすn∈Zn\in\Zの全体が下に有界であるものを形式的 Laurent 級数 (formal Laurent series) とよび、F(n)F(n)を[xn]F[x^{n}]Fと書いてF=∑n∈Z([xn]F)xnF=\sum_{n\in\Z}([x^{n}]F)x^{n}と表す。形式的 Laurent 級数の全体をQ((x))\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]]\Q[[x]]である。

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

  1. F,G∈Q((x))F,G\in\Q((x))に対しord⁡(FG)=ord⁡(F)+ord⁡(G)\operatorname{ord}(FG)=\operatorname{ord}(F)+\operatorname{ord}(G)である。
  2. F≠0F\ne0ならばFFはQ((x))\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))\Q((x))は積について閉じている。

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

結合性。結合性だけは、係数の三重和を直接に扱うかわりに§E16.1 命題 1.2へ帰着させる。整数kkとF∈Q((x))F\in\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\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\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\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]]\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]]\Q[[x]]の元については、[xn](AB)[x^{n}](AB)の定義に現れる和のうち添字が負である項の係数が00であるから、Q((x))\Q((x))の積は Cauchy 積に一致する。ゆえに§E16.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))\Q((x))は単位元をもつ可換環であり、ord⁡(F)≥0\operatorname{ord}(F)\ge0を満たす元の全体Q[[x]]\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\Q[[x]]であり、いずれも位数00である。FG=xp+qF0G0FG=x^{p+q}F_0G_0であり、§E16.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\Q[[x]]と置く。[x0]F0≠0[x^{0}]F_0\ne0であるから定理 1.1によりF0F_0はQ[[x]]\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))\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))\Q((x))の元が定められる。族の各項がQ[[x]]\Q[[x]]に属する場合、この定義は§E16.2 定義 2.3に一致する。F∈Q((x))F\in\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))\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\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\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\Q((x))に対し、族(([xn]F) Gn)n∈Z\bigl(([x^{n}]F)\,G^{n}\bigr)_{n\in\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\Z}\bigl([x^{n}]F\bigr)G^{n}

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

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

  1. x∘G=Gx\circ G=Gである。
  2. 任意のF∈Q((x))F\in\Q((x))に対しF∘x=FF\circ x=Fである。
  3. 任意のF∈Q((x))F\in\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\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\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\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\Q((x))に対し、[xn]F′=(n+1)[xn+1]F[x^{n}]F'=(n+1)[x^{n+1}]F（n∈Zn\in\Z）で定まるF′∈Q((x))F'\in\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\Q((x))、λ∈Q\lambda\in\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\Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとき、任意のF∈Q((x))F\in\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\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\Q[[x]]がord⁡(G)=1\operatorname{ord}(G)=1を満たすとする。任意のF∈Q((x))F\in\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\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]]\Q[[x]]の可逆元であり、U′∈Q[[x]]U'\in\Q[[x]]であるからU′/U∈Q[[x]]U'/U\in\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\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\Q[[x]]がただ一つ存在する。さらに、このGˉ\bar GはGˉ∘G=x\bar G\circ G=xも満たす。Gˉ\bar GをGGの合成逆元 (compositional inverse) とよぶ。

証明.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\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\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\Q[[x]]が[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0を満たすとし、Gˉ\bar Gをその合成逆元とする。任意のH∈Q((x))H\in\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\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\Q[[x]]がただ一つ存在する。さらに、任意のH∈Q[[x]]H\in\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]]\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\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]]\C[[x]]において述べられているが、両辺の係数はすべて有理数であり、§E16.1 命題 1.2によりQ[[x]]\Q[[x]]はC[[x]]\C[[x]]の部分環であるから、Q[[x]]\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.定義 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}である。

§E16.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が得られ、すべて一致する。

注意 6.7. 多変数の反転公式、係数の解析的な漸近評価、および形式的冪級数の代数的・微分方程式的な性質は、本記事では扱っていない。

7 演習

問題 7.1.

  1. G∈Q[[x]]G\in\Q[[x]]が[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0を満たし、すべての整数m≥0m\ge0について[x2m]G=0[x^{2m}]G=0であるとする。GGの合成逆元Gˉ\bar Gも、すべての整数m≥0m\ge0について[x2m]Gˉ=0[x^{2m}]\bar G=0を満たすことを証明せよ。さらに、G=x−x3G=x-x^{3}の合成逆元の第11係数から第77係数までを求めよ。
  2. G∈Q[[x]]G\in\Q[[x]]とする。ord⁡(H)=1\operatorname{ord}(H)=1かつG∘H=xG\circ H=xを満たすH∈Q[[x]]H\in\Q[[x]]が存在するならば、[x0]G=0[x^{0}]G=0かつ[x1]G≠0[x^{1}]G\ne0であることを証明せよ。さらにG=x2G=x^{2}に対してG∘Gˉ=xG\circ\bar G=xを満たすGˉ∈Q[[x]]\bar G\in\Q[[x]]が存在しないことを証明せよ。
  3. G∈Q((x))G\in\Q((x))をG≠0G\ne0かつord⁡(G)=d\operatorname{ord}(G)=dを満たす元とする。res⁡(G−1G′)=d\operatorname{res}(G^{-1}G')=dを証明せよ。これを用いて、d≠0d\ne0のときG−1G′G^{-1}G'がどのF∈Q((x))F\in\Q((x))の形式微分にも等しくないことを示せ。さらに、G=x+x2G=x+x^{2}についてres⁡(G−1G′)=1\operatorname{res}(G^{-1}G')=1を直接の計算で確かめよ。
  4. 定理 5.1の仮定のもとで、任意のH∈Q((x))H\in\Q((x))と任意の整数nn（n=0n=0を含む）に対し[xn](H∘Gˉ)=res⁡(H G′ G−n−1)[x^{n}]\bigl(H\circ\bar G\bigr)=\operatorname{res}\bigl(H\,G'\,G^{-n-1}\bigr)が成り立つことを証明せよ。これをG=x−x2G=x-x^{2}とH=(1−2x)−1H=(1-2x)^{-1}に適用して、GGの合成逆元Gˉ\bar Gについて(1−2Gˉ)−1=∑n≥0(2nn)xn(1-2\bar G)^{-1}=\sum_{n\ge0}\binom{2n}{n}x^{n}を示せ。
  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}と一致することを確かめよ。
解答.

(1)を示す。σ=−x\sigma=-xと置くとord⁡(σ)=1\operatorname{ord}(\sigma)=1である。定義 3.1により、F∈Q[[x]]F\in\Q[[x]]に対してF∘σ=∑n≥0([xn]F)(−x)nF\circ\sigma=\sum_{n\ge0}([x^{n}]F)(-x)^{n}であるから、[xn](F∘σ)=(−1)n[xn]F[x^{n}](F\circ\sigma)=(-1)^{n}[x^{n}]Fである。とくにσ∘σ=x\sigma\circ\sigma=xである。F∘σ=−FF\circ\sigma=-Fであることは、すべてのm≥0m\ge0について[x2m]F=0[x^{2m}]F=0であることと同値である。実際、nnが奇数のとき(−1)n[xn]F=−[xn]F(-1)^{n}[x^{n}]F=-[x^{n}]Fはつねに成り立ち、nnが偶数のとき[xn]F=−[xn]F[x^{n}]F=-[x^{n}]Fは[xn]F=0[x^{n}]F=0と同値である。また、ord⁡(F)=1\operatorname{ord}(F)=1のとき、定義 3.1によりσ∘F=−F1=−F\sigma\circ F=-F^{1}=-Fである。

仮定によりG∘σ=−G=σ∘GG\circ\sigma=-G=\sigma\circ Gである。命題 3.4により、位数11の元の合成は位数11であるから、H=σ∘(Gˉ∘σ)H=\sigma\circ(\bar G\circ\sigma)は位数11の元である。命題 3.4を繰り返し用い、定理 4.1のG∘Gˉ=xG\circ\bar G=xと補題 3.2 (1)のx∘σ=σx\circ\sigma=\sigmaを用いると

G∘H=(G∘σ)∘(Gˉ∘σ)=(σ∘G)∘(Gˉ∘σ)=σ∘((G∘Gˉ)∘σ)=σ∘(x∘σ)=σ∘σ=xG\circ H=(G\circ\sigma)\circ(\bar G\circ\sigma)=(\sigma\circ G)\circ(\bar G\circ\sigma)=\sigma\circ\bigl((G\circ\bar G)\circ\sigma\bigr)=\sigma\circ(x\circ\sigma)=\sigma\circ\sigma=x

である。定理 4.1の一意性によりH=GˉH=\bar Gである。両辺に左からσ\sigmaを合成すると、命題 3.4と補題 3.2 (1)により

σ∘Gˉ=σ∘H=(σ∘σ)∘(Gˉ∘σ)=x∘(Gˉ∘σ)=Gˉ∘σ\sigma\circ\bar G=\sigma\circ H=(\sigma\circ\sigma)\circ(\bar G\circ\sigma)=x\circ(\bar G\circ\sigma)=\bar G\circ\sigma

である。左辺は−Gˉ-\bar GであるからGˉ∘σ=−Gˉ\bar G\circ\sigma=-\bar Gであり、第一段により、すべてのm≥0m\ge0について[x2m]Gˉ=0[x^{2m}]\bar G=0である。

G=x−x3G=x-x^{3}とする。[x0]G=0[x^{0}]G=0、[x1]G=1[x^{1}]G=1であり、偶数次の係数はすべて00である。Gˉ=∑n≥1bnxn\bar G=\sum_{n\ge1}b_nx^{n}と書くと、前段によりb2=b4=b6=0b_2=b_4=b_6=0である。定義 3.1によりG∘Gˉ=Gˉ−Gˉ3G\circ\bar G=\bar G-\bar G^{3}であるから、G∘Gˉ=xG\circ\bar G=xはGˉ=x+Gˉ3\bar G=x+\bar G^{3}と同値である。命題 2.2 (1)によりord⁡(Gˉ3)=3\operatorname{ord}(\bar G^{3})=3であるから、第11係数を比べてb1=1b_1=1である。Gˉ=xV\bar G=xV、V=1+b3x2+b5x4+b7x6+⋯V=1+b_3x^{2}+b_5x^{4}+b_7x^{6}+\cdotsと置くとGˉ3=x3V3\bar G^{3}=x^{3}V^{3}であり、n≥3n\ge3についてbn=[xn]Gˉ3=[xn−3]V3b_n=[x^{n}]\bar G^{3}=[x^{n-3}]V^{3}である。§E16.2 補題 2.6を三つの因子VVに適用すると、VVの奇数次の係数は00であるから

[x0]V3=1,[x2]V3=3b3,[x4]V3=3b5+3b32[x^{0}]V^{3}=1,\qquad [x^{2}]V^{3}=3b_3,\qquad [x^{4}]V^{3}=3b_5+3b_3^{2}

である。[x4]V3[x^{4}]V^{3}では、和が44である偶数の組(4,0,0)(4,0,0)の並べ替え33通りが3b53b_5を、(2,2,0)(2,2,0)の並べ替え33通りが3b323b_3^{2}を与える。ゆえにb3=1b_3=1、b5=3b3=3b_5=3b_3=3、b7=3b5+3b32=12b_7=3b_5+3b_3^{2}=12であり、第11係数から第77係数までは

b1=1,b2=0,b3=1,b4=0,b5=3,b6=0,b7=12b_1=1,\quad b_2=0,\quad b_3=1,\quad b_4=0,\quad b_5=3,\quad b_6=0,\quad b_7=12

である。検算として、Gˉ3\bar G^{3}の第3,5,73,5,7係数は11、33、1212であり、Gˉ−Gˉ3\bar G-\bar G^{3}の第77係数まではxxに一致する。

(2)を示す。gk=[xk]Gg_k=[x^{k}]G、h1=[x1]Hh_1=[x^{1}]Hと書く。命題 2.2 (2)によりord⁡(Hk)=k\operatorname{ord}(H^{k})=kであるから、定義 3.1と定義 2.3により、G∘H=∑k≥0gkHkG\circ H=\sum_{k\ge0}g_kH^{k}の第00係数にはk=0k=0の項だけが寄与し、第11係数にはk≤1k\le1の項だけが寄与する。H0=1H^{0}=1の第00係数は11、第11係数は00であるから

[x0](G∘H)=g0,[x1](G∘H)=g1h1[x^{0}](G\circ H)=g_0,\qquad [x^{1}](G\circ H)=g_1h_1

である。G∘H=xG\circ H=xならば、g0=[x0]x=0g_0=[x^{0}]x=0であり、g1h1=[x1]x=1g_1h_1=[x^{1}]x=1であるからg1≠0g_1\ne0である。したがって、定理 4.1の仮定[x0]G=0[x^{0}]G=0、[x1]G≠0[x^{1}]G\ne0は、位数11の右合成逆元が存在するための必要条件でもある。とくに[x0]G=[x1]G=0[x^{0}]G=[x^{1}]G=0ならば、位数11のどのHHについても[x1](G∘H)=0≠1[x^{1}](G\circ H)=0\ne1である。

G=x2G=x^{2}とする。定義 3.1により、G∘GˉG\circ\bar Gが定義されるのはord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1のときであり、[xn]G[x^{n}]Gはn=2n=2のときだけ11で他は00であるから、G∘Gˉ=Gˉ2G\circ\bar G=\bar G^{2}である。命題 2.2 (1)によりord⁡(Gˉ2)=2\operatorname{ord}(\bar G^{2})=2であるが、ord⁡(x)=1\operatorname{ord}(x)=1であるからGˉ2≠x\bar G^{2}\ne xである。ゆえにG∘Gˉ=xG\circ\bar G=xを満たすGˉ∈Q[[x]]\bar G\in\Q[[x]]は存在しない。合成を積Gˉ2\bar G^{2}と読んでord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1でないGˉ∈Q[[x]]\bar G\in\Q[[x]]まで許しても、結論は変わらない。§E16.2 補題 2.2によりord⁡(Gˉ2)=2ord⁡(Gˉ)\operatorname{ord}(\bar G^{2})=2\operatorname{ord}(\bar G)は偶数または∞\inftyであり、ord⁡(x)=1\operatorname{ord}(x)=1に等しくならないからである。

(3)を示す。c=[xd]G≠0c=[x^{d}]G\ne0と置き、U=c−1x−dGU=c^{-1}x^{-d}Gとする。定義 2.1の積により[xm](x−dG)=[xm+d]G[x^{m}](x^{-d}G)=[x^{m+d}]Gであるから、UUの第mm係数はm<0m<0のとき00、m=0m=0のとき11である。ゆえにU∈Q[[x]]U\in\Q[[x]]かつ[x0]U=1[x^{0}]U=1であり、G=cxdUG=cx^{d}Uである。定義 3.5により(xd)′=dxd−1(x^{d})'=dx^{d-1}であるから、命題 3.6 (1)と命題 3.6 (2)によりG′=c d xd−1U+cxdU′G'=c\,d\,x^{d-1}U+cx^{d}U'である。定理 1.1によりUUはQ[[x]]\Q[[x]]の可逆元であり、G⋅c−1x−dU−1=1G\cdot c^{-1}x^{-d}U^{-1}=1であるからG−1=c−1x−dU−1G^{-1}=c^{-1}x^{-d}U^{-1}である。命題 2.2によりQ((x))\Q((x))は可換環であるから

G−1G′=c−1x−dU−1(c d xd−1U+cxdU′)=d x−1+U′U−1G^{-1}G'=c^{-1}x^{-d}U^{-1}\bigl(c\,d\,x^{d-1}U+cx^{d}U'\bigr)=d\,x^{-1}+U'U^{-1}

である。U′U'とU−1U^{-1}はQ[[x]]\Q[[x]]の元であるからU′U−1∈Q[[x]]U'U^{-1}\in\Q[[x]]であり、その第−1-1係数は00である。係数は和について加法的であるから、res⁡(G−1G′)=d\operatorname{res}(G^{-1}G')=dである。

d≠0d\ne0とする。G−1G′=F′G^{-1}G'=F'を満たすF∈Q((x))F\in\Q((x))が存在したとすると、補題 3.8によりres⁡(G−1G′)=res⁡(F′)=0\operatorname{res}(G^{-1}G')=\operatorname{res}(F')=0となり、前段のres⁡(G−1G′)=d≠0\operatorname{res}(G^{-1}G')=d\ne0に反する。ゆえに、G−1G′G^{-1}G'はどのF∈Q((x))F\in\Q((x))の形式微分にも等しくない。d=1d=1の場合には、とくにG−1G′G^{-1}G'は(Gn+1)′(G^{n+1})'の定数倍の形に表すことができない。

G=x+x2G=x+x^{2}について直接に計算する。G=x(1+x)G=x(1+x)であり、G′=1+2xG'=1+2xである。P=∑k≥0(−1)kxkP=\sum_{k\ge0}(-1)^{k}x^{k}と置くと、(1+x)P(1+x)Pの第00係数は11、第mm係数（m≥1m\ge1）は(−1)m+(−1)m−1=0(-1)^{m}+(-1)^{m-1}=0であるから、(1+x)P=1(1+x)P=1である。ゆえにG⋅x−1P=(1+x)P=1G\cdot x^{-1}P=(1+x)P=1であり、G−1=x−1P=∑k≥0(−1)kxk−1G^{-1}=x^{-1}P=\sum_{k\ge0}(-1)^{k}x^{k-1}である。したがって

G−1G′=x−1P (1+2x)=∑k≥0(−1)kxk−1+2∑k≥0(−1)kxkG^{-1}G'=x^{-1}P\,(1+2x)=\sum_{k\ge0}(-1)^{k}x^{k-1}+2\sum_{k\ge0}(-1)^{k}x^{k}

である。第二の和はQ[[x]]\Q[[x]]の元であり、その第−1-1係数は00である。第一の和の第−1-1係数はk=0k=0の項の11である。ゆえにres⁡(G−1G′)=1\operatorname{res}(G^{-1}G')=1である。

(4)を示す。H∈Q((x))H\in\Q((x))と整数nnを取り、F=H∘GˉF=H\circ\bar Gと置く。定理 4.1によりord⁡(Gˉ)=1\operatorname{ord}(\bar G)=1であるから、F∈Q((x))F\in\Q((x))が定まる。命題 3.4を位数11のGˉ\bar GとGGに適用し、定理 4.1のGˉ∘G=x\bar G\circ G=xと補題 3.2 (2)を用いると

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

である。K=Fx−n−1K=Fx^{-n-1}と置く。定義 2.1の積により[x−1](Fx−n−1)=∑i+j=−1([xi]F)([xj]x−n−1)=[xn]F[x^{-1}](Fx^{-n-1})=\sum_{i+j=-1}([x^{i}]F)([x^{j}]x^{-n-1})=[x^{n}]Fであるから、res⁡(K)=[xn]F\operatorname{res}(K)=[x^{n}]Fである。命題 3.3の積と整数べきについての主張と補題 3.2 (1)により

K∘G=(F∘G)(x−n−1∘G)=H (x∘G)−n−1=H G−n−1K\circ G=(F\circ G)\bigl(x^{-n-1}\circ G\bigr)=H\,(x\circ G)^{-n-1}=H\,G^{-n-1}

である。補題 3.9をKKに適用し、命題 2.2により積の順序を入れ替えると

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

を得る。この議論はn≠0n\ne0を用いないので、等式はn=0n=0でも成り立つ。

適用する。G=x−x2G=x-x^{2}は[x0]G=0[x^{0}]G=0、[x1]G=1≠0[x^{1}]G=1\ne0を満たす。定理 1.1により1−2x1-2xはQ[[x]]\Q[[x]]の可逆元であり、H=(1−2x)−1∈Q[[x]]H=(1-2x)^{-1}\in\Q[[x]]が定まる。定義 3.5によりG′=1−2xG'=1-2xであるからHG′=1HG'=1であり、前段により、n≥0n\ge0に対して

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

である。G=x(1−x)G=x(1-x)であり、定理 1.1により1−x1-xは可逆であるから、G−n−1=x−n−1(1−x)−n−1G^{-n-1}=x^{-n-1}(1-x)^{-n-1}である。前段と同じ計算により、L∈Q((x))L\in\Q((x))に対してres⁡(x−n−1L)=[xn]L\operatorname{res}(x^{-n-1}L)=[x^{n}]Lであるから、res⁡(G−n−1)=[xn](1−x)−n−1\operatorname{res}(G^{-n-1})=[x^{n}](1-x)^{-n-1}である。§D2.4 命題 5.2をα=1\alpha=1、m=n+1m=n+1として用い、定理 6.2の証明と同じくQ[[x]]\Q[[x]]の等式として読むと、[xn](1−x)−n−1=(2nn)[x^{n}](1-x)^{-n-1}=\binom{2n}{n}である。ゆえにH∘Gˉ=∑n≥0(2nn)xnH\circ\bar G=\sum_{n\ge0}\binom{2n}{n}x^{n}である。他方、命題 3.3によりH∘Gˉ=((1−2x)∘Gˉ)−1H\circ\bar G=\bigl((1-2x)\circ\bar G\bigr)^{-1}であり、同命題の和の保存と、1∘Gˉ=Gˉ0=11\circ\bar G=\bar G^{0}=1、補題 3.2 (1)のx∘Gˉ=Gˉx\circ\bar G=\bar Gにより(1−2x)∘Gˉ=1−2Gˉ(1-2x)\circ\bar G=1-2\bar Gである。したがって(1−2Gˉ)−1=∑n≥0(2nn)xn(1-2\bar G)^{-1}=\sum_{n\ge0}\binom{2n}{n}x^{n}である。定理 6.2の証明のW=xC(x)W=xC(x)はord⁡(W)=1\operatorname{ord}(W)=1とW−W2=xW-W^{2}=x、すなわちG∘W=xG\circ W=xを満たすので、定理 4.1の一意性によりGˉ=xC(x)\bar G=xC(x)である。ゆえにこの等式は(1−2xC(x))−1=∑n≥0(2nn)xn\bigl(1-2xC(x)\bigr)^{-1}=\sum_{n\ge0}\binom{2n}{n}x^{n}と書くこともできる。n=0,1,2,3n=0,1,2,3について、例 6.3の値から1−2Gˉ=1−2x−2x2−4x3−⋯1-2\bar G=1-2x-2x^{2}-4x^{3}-\cdotsであり、(1+2x+6x2+20x3)(1−2x−2x2−4x3)(1+2x+6x^{2}+20x^{3})(1-2x-2x^{2}-4x^{3})の第1,2,31,2,3係数は2−2=02-2=0、6−4−2=06-4-2=0、20−12−4−4=020-12-4-4=0である。

(5)では、ϕ(x)=1+x\phi(x)=1+xは[x0]ϕ=1≠0[x^{0}]\phi=1\ne0を満たすので、系 5.2により、W=x(ϕ∘W)W=x(\phi\circ W)とord⁡(W)=1\operatorname{ord}(W)=1を満たすW∈Q[[x]]W\in\Q[[x]]がただ一つ存在する。命題 3.3の和の保存と、1∘W=W0=11\circ W=W^{0}=1、補題 3.2 (1)のx∘W=Wx\circ W=Wによりϕ∘W=1+W\phi\circ W=1+Wであるから、この関数方程式はW=x(1+W)W=x(1+W)である。

公式から係数を求める。n≥1n\ge1に対して[xn]W=1n[xn−1](1+x)n[x^{n}]W=\frac1n[x^{n-1}](1+x)^{n}である。[xm](1+x)[x^{m}](1+x)はm∈{0,1}m\in\{0,1\}のとき11、それ以外のとき00であるから、§E16.2 補題 2.6をnn個の因子1+x1+xに適用すると、[xn−1](1+x)n[x^{n-1}](1+x)^{n}は、各成分が00または11で総和がn−1n-1である組(n1,…,nn)(n_1,\dots,n_n)の個数に等しい。そのような組は、ちょうど一つの成分が00である組であり、nn個ある。ゆえにn≥1n\ge1について[xn]W=1n⋅n=1[x^{n}]W=\frac1n\cdot n=1であり、[x0]W=0[x^{0}]W=0とあわせてW=∑n≥1xnW=\sum_{n\ge1}x^{n}である。

関数方程式を直接に解く。W=x(1+W)W=x(1+W)はW−xW=xW-xW=x、すなわち(1−x)W=x(1-x)W=xと同値である。§E16.2 補題 2.7をk=1k=1として用いると、1−x1-xは可逆であり(1−x)−1=∑j≥0xj(1-x)^{-1}=\sum_{j\ge0}x^{j}であるから、W=x(1−x)−1=∑j≥0xj+1=∑n≥1xnW=x(1-x)^{-1}=\sum_{j\ge0}x^{j+1}=\sum_{n\ge1}x^{n}である。この式は公式から求めた係数と一致する。

(6)では、ϕ(x)=(1−x)−1\phi(x)=(1-x)^{-1}に対する系 5.2のWWを考える。H=x2H=x^{2}とすると、定義 3.1によりH∘W=W2H\circ W=W^{2}であり、定義 3.5によりH′=2xH'=2xである。K∈Q[[x]]K\in\Q[[x]]に対して、m≥1m\ge1のとき[xm](xK)=[xm−1]K[x^{m}](xK)=[x^{m-1}]K、m=0m=0のとき[x0](xK)=0[x^{0}](xK)=0である。系 5.2により、n≥1n\ge1に対して

[xn]W2=1n[xn−1](2x ϕn)[x^{n}]W^{2}=\frac1n[x^{n-1}]\bigl(2x\,\phi^{n}\bigr)

である。n=1n=1のとき右辺は[x0](2xϕ)=0[x^{0}](2x\phi)=0であるから、[x1]W2=0[x^{1}]W^{2}=0である。n≥2n\ge2のとき右辺は2n[xn−2](1−x)−n\frac2n[x^{n-2}](1-x)^{-n}に等しい。§D2.4 命題 5.2をα=1\alpha=1、m=nm=nとして用い、定理 6.2の証明と同じくQ[[x]]\Q[[x]]の等式として読むと、[xn−2](1−x)−n=((n−2)+n−1n−1)=(2n−3n−1)[x^{n-2}](1-x)^{-n}=\binom{(n-2)+n-1}{n-1}=\binom{2n-3}{n-1}である。ゆえに

[xn]W2=2n(2n−3n−1)(n≥2)[x^{n}]W^{2}=\frac2n\binom{2n-3}{n-1}\qquad(n\ge2)

である。

n=4n=4のとき、この式は[x4]W2=24(53)=12⋅10=5[x^{4}]W^{2}=\frac24\binom53=\frac12\cdot10=5を与える。他方、定理 6.2の証明により、このWWはW=xC(x)W=xC(x)であり、[xm]W=Cm−1[x^{m}]W=C_{m-1}（m≥1m\ge1）、[x0]W=0[x^{0}]W=0である。例 6.3の値C0=1C_0=1、C1=1C_1=1、C2=2C_2=2から[x1]W=1[x^{1}]W=1、[x2]W=1[x^{2}]W=1、[x3]W=2[x^{3}]W=2であるから、

[x4]W2=∑i+j=4([xi]W)([xj]W)=1⋅2+1⋅1+2⋅1=5[x^{4}]W^{2}=\sum_{i+j=4}\bigl([x^{i}]W\bigr)\bigl([x^{j}]W\bigr)=1\cdot2+1\cdot1+2\cdot1=5

である。ここでi=0i=0またはj=0j=0の項は[x0]W=0[x^{0}]W=0により00である。二つの値は一致する。▨

参考文献

  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.形式的冪級数の代数的な取り扱いと単純生成木の関数方程式を参考にした。

前提記事