§E16.1指数型母関数

最終更新

数え上げの対象には、要素が互いに区別される構造がある。nn人の並べ方、nn個の相異なる元の集合分割、nn頂点上のラベル付き木は、いずれも要素に11からnnまでの番号が付いた構造である。このような構造では、大きさkkの部分構造と大きさn−kn-kの部分構造を組み合わせるときに、nn個の番号をどちらへ配るかという選択が加わる。通常母関数の積から得られる畳み込み∑jajbn−j\sum_j a_j b_{n-j}は、この選択の個数を因子として含まない。

本記事では、番号の付いた構造を扱うための母関数として指数型母関数を定義し、通常母関数との違いを二項型の畳み込みとして確定する。そのうえで、二つの構造を並置するラベル付き積、部分構造を順に並べる列、部分構造を無順序に集める集合という三つの構成について、母関数の側での対応則を、ラベル集合の分割を数えることによって完全に証明する。

1 形式的冪級数の環

本記事では、係数を有理数体Q\Qに取る。形式的冪級数の和、Cauchy 積および係数抽出[xn][x^{n}]の定義は§D2.4 定義 4.1で与えられる。同記事では係数体を複素数体に取っているが、定義そのものは任意の可換環に係数を取っても意味をもつ。本記事では係数環を一般にした形で定義を置く。

定義 1.1.RRを単位元11をもつ可換環とする。非負整数で添字づけられたRRの元の族の全体をR[[x]]R[[x]]と書き、その元を RRに係数をもつ形式的冪級数 (formal power series over R) という。F∈R[[x]]F\in R[[x]]の第nn成分を[xn]F[x^{n}]Fと書き、FFの第nn係数という。二つの元は係数がすべて一致するとき等しいと定め、和と積を

[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)

で定める。第二式の右辺はi+j=ni+j=nを満たす非負整数の対の全体にわたる有限和であり、これを Cauchy 積という。R=CR=\Cとすると、この定義は§D2.4 定義 4.1の定義に一致する。

本記事では、この後で有限個の因子の積を並べ替え、分配法則によって展開する操作を繰り返し用いる。これらの操作はR[[x]]R[[x]]が可換環であることに依拠する。§D2.4 定義 4.1では演算を定めるだけで、その演算が環をなすことは述べられていない。そのため、R[[x]]R[[x]]が単位元をもつ可換環であることを、ここで証明する。

命題 1.2.RRを単位元11をもつ可換環とする。R[[x]]R[[x]]は定義 1.1の和と Cauchy 積について、単位元をもつ可換環である。すなわち次が成り立つ。

  1. (R[[x]],+)(R[[x]],+)は可換群である。零元はすべての係数が00である元であり、FFの加法逆元は[xn](−F)=−[xn]F[x^{n}](-F)=-[x^{n}]Fで定まる元である。
  2. Cauchy 積は可換である。
  3. Cauchy 積は結合的である。
  4. 任意のF,G,H∈R[[x]]F,G,H\in R[[x]]に対しF(G+H)=FG+FHF(G+H)=FG+FHが成り立つ。
  5. [x0]=1[x^{0}]=1かつ他の係数が00である元11は、Cauchy 積の単位元である。

とくにQ[[x]]\Q[[x]]とC[[x]]\C[[x]]はいずれも単位元をもつ可換環であり、Q[[x]]\Q[[x]]はC[[x]]\C[[x]]の部分環である。

証明. 以下fi=[xi]Ff_i=[x^{i}]F、gj=[xj]Gg_j=[x^{j}]G、hk=[xk]Hh_k=[x^{k}]Hと書く。

主張 (1)を示す。和は係数ごとに定義されており、(R,+)(R,+)が可換群であるから、結合法則、交換法則、零元の存在および加法逆元の存在は各係数について成り立つ。係数がすべて一致することが元の一致であるから、(R[[x]],+)(R[[x]],+)は可換群である。

主張 (2)を示す。RRの積が可換であることと、i+j=ni+j=nを満たす対(i,j)(i,j)を(j,i)(j,i)へ写す対応が同じ添字集合の上の全単射であることから、各nnについて

[xn](FG)=∑i+j=nfigj=∑j+i=ngjfi=[xn](GF)[x^{n}](FG)=\sum_{i+j=n}f_ig_j=\sum_{j+i=n}g_jf_i=[x^{n}](GF)

である。

主張 (3)を示す。定義を二度用いると

[xn]((FG)H)=∑m+k=n(∑i+j=mfigj)hk[x^{n}]\bigl((FG)H\bigr)=\sum_{m+k=n}\Bigl(\sum_{i+j=m}f_ig_j\Bigr)h_k

である。内側の有限和にhkh_kを掛ける操作は、RRの分配法則を有限回用いて各項へ分配することができ、RRの積の結合法則により(figj)hk=fi(gjhk)(f_ig_j)h_k=f_i(g_jh_k)である。ゆえに右辺は、i+j+k=ni+j+k=nを満たす非負整数の三つ組(i,j,k)(i,j,k)の全体にわたる有限和

∑i,j,k≥0i+j+k=nfigjhk\sum_{\substack{i,j,k\ge0\\ i+j+k=n}}f_ig_jh_k

に等しい。ここで、対(m,k)(m,k)とi+j=mi+j=mを満たす対(i,j)(i,j)の組を三つ組(i,j,k)(i,j,k)へ写す対応が全単射であることを用いた。同様に

[xn](F(GH))=∑i+m=nfi(∑j+k=mgjhk)=∑i,j,k≥0i+j+k=nfigjhk[x^{n}]\bigl(F(GH)\bigr)=\sum_{i+m=n}f_i\Bigl(\sum_{j+k=m}g_jh_k\Bigr) =\sum_{\substack{i,j,k\ge0\\ i+j+k=n}}f_ig_jh_k

である。二つの式は同じ有限集合にわたる同じ項の和であるから等しい。nnは任意であったから(FG)H=F(GH)(FG)H=F(GH)である。

主張 (4)を示す。RRの分配法則と有限和の分割により、各nnについて

[xn](F(G+H))=∑i+j=nfi(gj+hj)=∑i+j=nfigj+∑i+j=nfihj=[xn](FG)+[xn](FH)[x^{n}]\bigl(F(G+H)\bigr)=\sum_{i+j=n}f_i(g_j+h_j)=\sum_{i+j=n}f_ig_j+\sum_{i+j=n}f_ih_j=[x^{n}](FG)+[x^{n}](FH)

である。

主張 (5)を示す。[xj]1[x^{j}]1はj=0j=0のとき11、j≥1j\ge1のとき00であるから

[xn](F⋅1)=∑i+j=nfi [xj]1=fn[x^{n}](F\cdot1)=\sum_{i+j=n}f_i\,[x^{j}]1=f_n

であり、F⋅1=FF\cdot1=Fである。主張 (2)により1⋅F=F1\cdot F=Fでもある。

最後の主張を示す。Q\QとC\Cはいずれも単位元をもつ可換環であるから、主張 (1)から主張 (5)によりQ[[x]]\Q[[x]]とC[[x]]\C[[x]]は単位元をもつ可換環である。Q⊆C\Q\subseteq\Cであり、和と Cauchy 積は係数の和と積だけで定まるので、Q[[x]]\Q[[x]]はC[[x]]\C[[x]]の部分集合として同じ演算と同じ単位元をもつ。ゆえにQ[[x]]\Q[[x]]はC[[x]]\C[[x]]の部分環である。▨

以下、断りのないかぎり係数環をQ\Qとする。列と集合の構成則では、定数項が零である級数のべきを無限個足し合わせる。その無限和の各係数が有限和であることを先に確かめる。

補題 1.3.B∈Q[[x]]B\in\Q[[x]]が[x0]B=0[x^{0}]B=0を満たすとする。このとき、次が成り立つ。

  1. 整数k≥0k\ge0とn≥0n\ge0に対し、k>nk>nならば[xn]Bk=0[x^{n}]B^{k}=0である。
  2. 有理数の列(λk)k≥0(\lambda_k)_{k\ge0}に対し、[xn]∑k≥0λkBk:=∑k=0nλk[xn]Bk[x^{n}]\sum_{k\ge0}\lambda_kB^{k}:=\sum_{k=0}^{n}\lambda_k[x^{n}]B^{k}と定めることにより、形式的冪級数∑k≥0λkBk∈Q[[x]]\sum_{k\ge0}\lambda_kB^{k}\in\Q[[x]]が定まる。
  3. (1−B)∑k≥0Bk=1\displaystyle(1-B)\sum_{k\ge0}B^{k}=1が成り立つ。したがって1−B1-BはQ[[x]]\Q[[x]]の可逆元であり、その逆元は∑k≥0Bk\sum_{k\ge0}B^{k}である。

証明. 以下、BkB^{k}は Cauchy 積によるkk個の因子の積を表す。命題 1.2 (3)により Cauchy 積は結合的であるから、この積は括弧の付け方によらず一つに定まり、Bk=B Bk−1B^{k}=B\,B^{k-1}が成り立つ。

主張 (1)をkkについての帰納法で示す。k=0k=0のときB0=1B^{0}=1であり、n<0n<0となるn≥0n\ge0は存在しないので主張は空に成り立つ。k≥1k\ge1とし、k−1k-1について主張が成り立つとする。Cauchy 積の定義（§D2.4 定義 4.1）により

[xn]Bk=∑j=0n([xj]B)([xn−j]Bk−1)[x^{n}]B^{k}=\sum_{j=0}^{n}\bigl([x^{j}]B\bigr)\bigl([x^{n-j}]B^{k-1}\bigr)

である。j=0j=0の項は[x0]B=0[x^{0}]B=0により消える。1≤j≤n1\le j\le nの項ではn−j≤n−1n-j\le n-1であり、k>nk>nからk−1>n−1≥n−jk-1>n-1\ge n-jが従うので、帰納法の仮定により[xn−j]Bk−1=0[x^{n-j}]B^{k-1}=0である。ゆえに[xn]Bk=0[x^{n}]B^{k}=0である。

(1)⇒\Rightarrow(2)を示す。実際、各nnについてk>nk>nの項は[xn]Bk=0[x^{n}]B^{k}=0を与えるので、∑k≥0λk[xn]Bk\sum_{k\ge0}\lambda_k[x^{n}]B^{k}はk=0,…,nk=0,\dots,nの有限和に等しい。各nnに対して有理数が一つ定まるので、形式的冪級数が一つ定まる。

主張 (3)を示す。S=∑k≥0BkS=\sum_{k\ge0}B^{k}と置く。nnを固定すると、主張 (1)により

[xn]S=∑k=0n[xn]Bk,[xn](BS)=∑j=0n([xj]B)([xn−j]S)[x^{n}]S=\sum_{k=0}^{n}[x^{n}]B^{k},\qquad [x^{n}](BS)=\sum_{j=0}^{n}\bigl([x^{j}]B\bigr)\bigl([x^{n-j}]S\bigr)

である。BSBSの係数を書き換える。[x0]B=0[x^{0}]B=0によりj≥1j\ge1の項だけが残り、n−j≤n−1n-j\le n-1であるから主張 (1)により[xn−j]S=∑k=0n−1[xn−j]Bk[x^{n-j}]S=\sum_{k=0}^{n-1}[x^{n-j}]B^{k}と書いてよい。よって

[xn](BS)=∑k=0n−1∑j=0n([xj]B)([xn−j]Bk)=∑k=0n−1[xn]Bk+1=∑k=1n[xn]Bk[x^{n}](BS)=\sum_{k=0}^{n-1}\sum_{j=0}^{n}\bigl([x^{j}]B\bigr)\bigl([x^{n-j}]B^{k}\bigr) =\sum_{k=0}^{n-1}[x^{n}]B^{k+1} =\sum_{k=1}^{n}[x^{n}]B^{k}

となる。ゆえに[xn](S−BS)=[xn]B0[x^{n}](S-BS)=[x^{n}]B^{0}であり、右辺はn=0n=0のとき11、n≥1n\ge1のとき00である。すなわち(1−B)S=1(1-B)S=1である。▨

主張 (2)により、定数項が零である級数に対して形式的な指数を定義することが可能になる。

定義 1.4.B∈Q[[x]]B\in\Q[[x]]が[x0]B=0[x^{0}]B=0を満たすとする。補題 1.3 (2)をλk=1/k!\lambda_k=1/k!として適用し、

exp⁡(B):=∑k≥01k!Bk∈Q[[x]]\exp(B):=\sum_{k\ge0}\frac{1}{k!}B^{k}\in\Q[[x]]

と定める。とくにexp⁡(x)=∑n≥0xn/n!\exp(x)=\sum_{n\ge0}x^{n}/n!である。

2 ラベル付き組合せクラス

番号の付いた構造を、番号の集合を替える操作と合わせて定式化する。番号の集合をラベル集合とよぶ。

定義 2.1. ラベル付き組合せクラス (labelled combinatorial class)A\mathcal Aとは、次の二つの対応の組であって、下の三条件を満たすもののことをいう。第一の対応は、正の整数からなる各有限集合UUに対して有限集合A[U]\mathcal A[U]を与える。第二の対応は、正の整数からなる有限集合の間の各全単射σ ⁣:U→V\sigma\colon U\to Vに対して写像A[σ] ⁣:A[U]→A[V]\mathcal A[\sigma]\colon\mathcal A[U]\to\mathcal A[V]を与える。

条件は次のとおりである。

  1. 各UUに対しA[idU]=idA[U]\mathcal A[\mathrm{id}_U]=\mathrm{id}_{\mathcal A[U]}が成り立つ。
  2. 全単射σ ⁣:U→V\sigma\colon U\to Vとτ ⁣:V→W\tau\colon V\to Wに対しA[τ∘σ]=A[τ]∘A[σ]\mathcal A[\tau\circ\sigma]=\mathcal A[\tau]\circ\mathcal A[\sigma]が成り立つ。
  3. 各UUに対しA[U]\mathcal A[U]は有限集合である。

A[U]\mathcal A[U]の元を、ラベル集合UUをもつ A\mathcal A-対象 (labelled object) とよび、∣U∣|U|をその大きさ (size) とよぶ。A[σ]\mathcal A[\sigma]をσ\sigmaによるラベルの付け替え (relabeling) とよぶ。

条件 (c)は、各大きさの対象が有限個であるという仮定にあたる。この仮定を外すと、以下で定義する母関数の係数が定まらない。

命題 2.2. ラベル付き組合せクラスA\mathcal Aと、正の整数からなる有限集合U,VU,Vについて∣U∣=∣V∣|U|=|V|ならば∣A[U]∣=∣A[V]∣|\mathcal A[U]|=|\mathcal A[V]|が成り立つ。

証明.∣U∣=∣V∣|U|=|V|であるから全単射σ ⁣:U→V\sigma\colon U\to Vが存在する。定義 2.1 条件 (a)と定義 2.1 条件 (b)により

A[σ−1]∘A[σ]=A[σ−1∘σ]=A[idU]=idA[U]\mathcal A[\sigma^{-1}]\circ\mathcal A[\sigma]=\mathcal A[\sigma^{-1}\circ\sigma]=\mathcal A[\mathrm{id}_U]=\mathrm{id}_{\mathcal A[U]}

であり、同様にA[σ]∘A[σ−1]=idA[V]\mathcal A[\sigma]\circ\mathcal A[\sigma^{-1}]=\mathrm{id}_{\mathcal A[V]}である。ゆえにA[σ]\mathcal A[\sigma]は全単射であり、全単射原理（§D2.2 命題 1.5）により∣A[U]∣=∣A[V]∣|\mathcal A[U]|=|\mathcal A[V]|である。▨

命題 2.2により、n≥0n\ge0に対して

an:=∣A[{1,2,…,n}]∣a_n:=\bigl|\mathcal A[\{1,2,\dots,n\}]\bigr|

と定めることができる。n=0n=0のときラベル集合は空集合である。数列(an)n≥0(a_n)_{n\ge0}をA\mathcal Aの計数列とよぶ。

定義 2.3. ラベル付き組合せクラスA\mathcal Aの計数列を(an)n≥0(a_n)_{n\ge0}とする。A\mathcal Aの指数型母関数 (exponential generating function) とは、形式的冪級数

A^(x)=∑n≥0ann!xn∈Q[[x]]\widehat A(x)=\sum_{n\ge0}\frac{a_n}{n!}x^{n}\in\Q[[x]]

のことをいう。すなわち[xn]A^(x)=an/n![x^{n}]\widehat A(x)=a_n/n!であり、an=n! [xn]A^(x)a_n=n!\,[x^{n}]\widehat A(x)である。

例 2.4. 次の三つはいずれも定義 2.1の条件を満たす。

線形順序のクラスL\mathcal L。L[U]\mathcal L[U]をUU上の全順序の全体とし、全単射σ ⁣:U→V\sigma\colon U\to Vに対しL[σ]\mathcal L[\sigma]を、全順序≤\leを「σ(u)≤′σ(u′)  ⟺  u≤u′\sigma(u)\le'\sigma(u')\iff u\le u'で定まるVV上の全順序≤′\le'」へ写す写像とする。UU上の全順序はUUの元の並べ方と一対一に対応するので、§D2.2 命題 3.1によりℓn=n!\ell_n=n!である。ゆえに

L^(x)=∑n≥0n!n!xn=∑n≥0xn.\widehat L(x)=\sum_{n\ge0}\frac{n!}{n!}x^{n}=\sum_{n\ge0}x^{n}.

補題 1.3 (3)をB=xB=xに適用するとL^(x)=(1−x)−1\widehat L(x)=(1-x)^{-1}である。

巡回順序のクラスC\mathcal C。空でないUUに対し、C[U]\mathcal C[U]を、UUの置換γ\gammaであって、γ\gammaの生成する巡回群のUUへの作用の軌道がただ一つであるものの全体とし、C[∅]=∅\mathcal C[\emptyset]=\emptysetとする。全単射σ ⁣:U→V\sigma\colon U\to Vに対してはC[σ](γ)=σ∘γ∘σ−1\mathcal C[\sigma](\gamma)=\sigma\circ\gamma\circ\sigma^{-1}と定める。n≥1n\ge1のとき、この種の置換は(n−1)!(n-1)!個である。実際、UUの元を一つ固定し、γ\gammaをその元から順に適用して得られる残りn−1n-1個の元の並びと対応させると、この対応は全単射である。ゆえにc0=0c_0=0、cn=(n−1)!c_n=(n-1)!(n≥1)(n\ge1)であり、

C^(x)=∑n≥1(n−1)!n!xn=∑n≥1xnn.\widehat C(x)=\sum_{n\ge1}\frac{(n-1)!}{n!}x^{n}=\sum_{n\ge1}\frac{x^{n}}{n}.

単一対象のクラスE\mathcal E。空でないUUに対しE[U]={U}\mathcal E[U]=\{U\}（要素が一つの集合）とし、E[∅]=∅\mathcal E[\emptyset]=\emptysetとする。全単射σ ⁣:U→V\sigma\colon U\to Vに対しE[σ](U)=V\mathcal E[\sigma](U)=Vと定める。e0=0e_0=0、en=1e_n=1(n≥1)(n\ge1)であり、

E^(x)=∑n≥1xnn!=exp⁡(x)−1.\widehat E(x)=\sum_{n\ge1}\frac{x^{n}}{n!}=\exp(x)-1.

3 通常母関数との違い

指数型母関数の積に対応する、数列の演算を確定する。

命題 3.1. 数列(an)n≥0(a_n)_{n\ge0}、(bn)n≥0(b_n)_{n\ge0}の指数型母関数をA^\widehat A、B^\widehat Bとすると、

n! [xn](A^(x)B^(x))=∑k=0n(nk)akbn−kn!\,[x^{n}]\bigl(\widehat A(x)\widehat B(x)\bigr)=\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}

が各n≥0n\ge0について成り立つ。

証明. Cauchy 積の定義（§D2.4 定義 4.1）により

[xn](A^B^)=∑k=0nakk!⋅bn−k(n−k)![x^{n}]\bigl(\widehat A\widehat B\bigr)=\sum_{k=0}^{n}\frac{a_k}{k!}\cdot\frac{b_{n-k}}{(n-k)!}

である。両辺にn!n!を掛け、各項についてn!k! (n−k)!=(nk)\dfrac{n!}{k!\,(n-k)!}=\dbinom{n}{k}（§D2.2 命題 3.1）を用いると主張を得る。▨

通常母関数の積から得られる畳み込みは∑kakbn−k\sum_{k}a_kb_{n-k}であり、二項係数を含まない。二項係数の有無によって数え上げの答えが変わることを、具体例で確かめる。

例 3.2.例 2.4の線形順序のクラスL\mathcal Lを二つ取り、ラベル集合UUを二つの部分へ分けたうえで各部分に全順序を与える構成を考える。U={1,2}U=\{1,2\}のとき、この構成の対象は次の66個である。

  • U1=∅U_1=\emptyset、U2={1,2}U_2=\{1,2\}とし、U2U_2上の全順序を1<21<2または2<12<1と取る。この形の対象は22個ある。
  • U1={1}U_1=\{1\}、U2={2}U_2=\{2\}とする。この形の対象は11個ある。
  • U1={2}U_1=\{2\}、U2={1}U_2=\{1\}とする。この形の対象は11個ある。
  • U1={1,2}U_1=\{1,2\}、U2=∅U_2=\emptysetとし、U1U_1上の全順序を二通りに取る。この形の対象は22個ある。

二項型の畳み込みは

∑k=02(2k)ℓkℓ2−k=(20)⋅1⋅2+(21)⋅1⋅1+(22)⋅2⋅1=2+2+2=6\sum_{k=0}^{2}\binom{2}{k}\ell_k\ell_{2-k}=\binom20\cdot1\cdot2+\binom21\cdot1\cdot1+\binom22\cdot2\cdot1=2+2+2=6

を与え、実際の個数66と一致する。これに対し通常母関数の積が与える畳み込みは

∑k=02ℓkℓ2−k=1⋅2+1⋅1+2⋅1=5\sum_{k=0}^{2}\ell_k\ell_{2-k}=1\cdot2+1\cdot1+2\cdot1=5

であり、正しい個数を与えない。差の11は、ラベル{1,2}\{1,2\}を大きさ11の二つの部分へ配る配り方が22通りあるのに対し、通常母関数の畳み込みが11通りとしか数えないことによる。

4 三つの構成

以下、A\mathcal AとB\mathcal Bをラベル付き組合せクラスとし、その計数列を(an)(a_n)、(bn)(b_n)とする。ラベル集合UUの分割とは、UUの空でない部分集合からなる族であって、互いに素であり、合併がUUに等しいもののことをいう。

定義 4.1.A\mathcal AとB\mathcal Bのラベル付き積 (labelled product)A⋆B\mathcal A\star\mathcal Bを次で定める。正の整数からなる有限集合UUに対し

(A⋆B)[U]={(U1,α,β) : U1⊆U, α∈A[U1], β∈B[U∖U1]}(\mathcal A\star\mathcal B)[U]=\bigl\{(U_1,\alpha,\beta)\ :\ U_1\subseteq U,\ \alpha\in\mathcal A[U_1],\ \beta\in\mathcal B[U\setminus U_1]\bigr\}

とし、全単射σ ⁣:U→V\sigma\colon U\to Vに対し

(A⋆B)[σ](U1,α,β)=(σ(U1), A[σ∣U1](α), B[σ∣U∖U1](β))(\mathcal A\star\mathcal B)[\sigma](U_1,\alpha,\beta)=\bigl(\sigma(U_1),\ \mathcal A[\sigma|_{U_1}](\alpha),\ \mathcal B[\sigma|_{U\setminus U_1}](\beta)\bigr)

と定める。ここでσ∣U1 ⁣:U1→σ(U1)\sigma|_{U_1}\colon U_1\to\sigma(U_1)とσ∣U∖U1 ⁣:U∖U1→V∖σ(U1)\sigma|_{U\setminus U_1}\colon U\setminus U_1\to V\setminus\sigma(U_1)はσ\sigmaの制限であり、いずれも全単射である。

定義 4.2.B[∅]=∅\mathcal B[\emptyset]=\emptysetを満たすラベル付き組合せクラスB\mathcal Bに対し、列のクラス (sequence class)Seq⁡(B)\operatorname{Seq}(\mathcal B)を次で定める。正の整数からなる有限集合UUに対し、Seq⁡(B)[U]\operatorname{Seq}(\mathcal B)[U]を、次を満たす有限列((U1,β1),…,(Uk,βk))\bigl((U_1,\beta_1),\dots,(U_k,\beta_k)\bigr)（k≥0k\ge0）の全体とする。

  1. U1,…,UkU_1,\dots,U_kは互いに素なUUの部分集合であり、U1∪⋯∪Uk=UU_1\cup\dots\cup U_k=Uである。
  2. 各iiについてβi∈B[Ui]\beta_i\in\mathcal B[U_i]である。

全単射σ ⁣:U→V\sigma\colon U\to Vに対しては、各成分を(σ(Ui),B[σ∣Ui](βi))\bigl(\sigma(U_i),\mathcal B[\sigma|_{U_i}](\beta_i)\bigr)へ置き換える写像をSeq⁡(B)[σ]\operatorname{Seq}(\mathcal B)[\sigma]とする。ちょうどkk個の成分をもつ列の全体をSeq⁡k(B)[U]\operatorname{Seq}_k(\mathcal B)[U]と書く。

定義 4.3.B[∅]=∅\mathcal B[\emptyset]=\emptysetを満たすラベル付き組合せクラスB\mathcal Bに対し、集合のクラス (set class)Set⁡(B)\operatorname{Set}(\mathcal B)を次で定める。正の整数からなる有限集合UUに対し、Set⁡(B)[U]\operatorname{Set}(\mathcal B)[U]を、次を満たす有限集合{(U1,β1),…,(Uk,βk)}\bigl\{(U_1,\beta_1),\dots,(U_k,\beta_k)\bigr\}（k≥0k\ge0）の全体とする。

  1. {U1,…,Uk}\{U_1,\dots,U_k\}はUUの分割である。ただしU=∅U=\emptysetのときはk=0k=0とし、空集合を唯一の対象とする。
  2. 各iiについてβi∈B[Ui]\beta_i\in\mathcal B[U_i]である。

全単射σ ⁣:U→V\sigma\colon U\to Vに対しては、定義 4.2と同じ規則で各成分を置き換える写像をSet⁡(B)[σ]\operatorname{Set}(\mathcal B)[\sigma]とする。ちょうどkk個の成分をもつ対象の全体をSet⁡k(B)[U]\operatorname{Set}_k(\mathcal B)[U]と書く。

命題 4.4.A\mathcal A、B\mathcal Bをラベル付き組合せクラスとし、列と集合の構成についてはB[∅]=∅\mathcal B[\emptyset]=\emptysetを仮定する。このときA⋆B\mathcal A\star\mathcal B、Seq⁡(B)\operatorname{Seq}(\mathcal B)、Set⁡(B)\operatorname{Set}(\mathcal B)はいずれも定義 2.1の三条件を満たす。

証明. 恒等写像と合成についての条件は、いずれの構成でも各成分ごとにA\mathcal AとB\mathcal Bの条件へ帰着する。実際、idU\mathrm{id}_Uの制限は各成分の恒等写像であり、τ∘σ\tau\circ\sigmaの制限はτ\tauの制限とσ\sigmaの制限の合成である。

有限性を示す。UUを固定しn=∣U∣n=|U|と置く。A⋆B\mathcal A\star\mathcal Bについては、U1U_1の取り方が高々2n2^{n}通りであり、各U1U_1に対してα\alphaとβ\betaの取り方が有限であるから、(A⋆B)[U](\mathcal A\star\mathcal B)[U]は有限集合である。

Seq⁡(B)\operatorname{Seq}(\mathcal B)については、まずkkがnn以下であることを示す。B[∅]=∅\mathcal B[\emptyset]=\emptysetであるから、βi∈B[Ui]\beta_i\in\mathcal B[U_i]が存在するためにはUi≠∅U_i\ne\emptysetでなければならない。U1,…,UkU_1,\dots,U_kは互いに素で合併がUUであるから、加法原理（§D2.2 定理 2.1）によりn=∑i=1k∣Ui∣≥kn=\sum_{i=1}^{k}|U_i|\ge kである。各k≤nk\le nについて、kk個の互いに素な部分集合の組の取り方は高々(2n)k(2^{n})^{k}通りであり、各組に対するβi\beta_iの取り方も有限であるから、Seq⁡(B)[U]\operatorname{Seq}(\mathcal B)[U]は有限個の有限集合の合併として有限集合である。Set⁡(B)[U]\operatorname{Set}(\mathcal B)[U]の各対象について、その成分を一列に並べるとSeq⁡(B)[U]\operatorname{Seq}(\mathcal B)[U]の対象が得られる。相異なる二つの対象は成分の集合が相異なるので、どのように並べても得られる列は相異なる。すなわちこの対応は単射であり、Set⁡(B)[U]\operatorname{Set}(\mathcal B)[U]も有限集合である。▨

5 構成則

5.1 証明方針

三つの構成則はいずれも、ラベル集合U={1,…,n}U=\{1,\dots,n\}の分割を数えることに帰着する。

ラベル付き積では、対象は「部分集合U1U_1の選択」と「U1U_1上のA\mathcal A-対象」と「補集合上のB\mathcal B-対象」の三つ組である。∣U1∣=k|U_1|=kとなるU1U_1の個数は(nk)\binom nkであるから、U1U_1の大きさで分類して加法原理を適用すると∑k(nk)akbn−k\sum_k\binom nk a_kb_{n-k}を得る。この和は命題 3.1の右辺にほかならない。

列では、成分の個数kkを固定した部分Seq⁡k(B)\operatorname{Seq}_k(\mathcal B)を考え、先頭の成分を切り離す全単射

Seq⁡k(B)[U]⟶(B⋆Seq⁡k−1(B))[U]\operatorname{Seq}_k(\mathcal B)[U]\longrightarrow\bigl(\mathcal B\star\operatorname{Seq}_{k-1}(\mathcal B)\bigr)[U]

を作る。この全単射とラベル付き積の構成則から、Seq⁡k(B)\operatorname{Seq}_k(\mathcal B)の母関数がB^k\widehat B^{k}に等しいことがkkについての帰納法で従う。B[∅]=∅\mathcal B[\emptyset]=\emptysetという仮定によってkkはnn以下に限られるので、kkについて足し合わせることができ、補題 1.3が和を(1−B^)−1(1-\widehat B)^{-1}と同定する。

集合では、成分の順序を忘れる写像Seq⁡k(B)[U]→Set⁡k(B)[U]\operatorname{Seq}_k(\mathcal B)[U]\to\operatorname{Set}_k(\mathcal B)[U]の各原像がちょうどk!k!個の元をもつことを示す。ここで、成分のラベル集合が互いに素かつ空でないという事実を用いる。加法原理により∣Set⁡k(B)[U]∣=∣Seq⁡k(B)[U]∣/k!|\operatorname{Set}_k(\mathcal B)[U]|=|\operatorname{Seq}_k(\mathcal B)[U]|/k!となり、kkについて足し合わせてexp⁡(B^)\exp(\widehat B)を得る。

定理 5.1. ラベル付き組合せクラスA\mathcal A、B\mathcal Bに対し

A⋆B^(x)=A^(x) B^(x)\widehat{\mathcal A\star\mathcal B}(x)=\widehat A(x)\,\widehat B(x)

が成り立つ。

証明.n≥0n\ge0を固定し、U={1,…,n}U=\{1,\dots,n\}と置く。(A⋆B)[U](\mathcal A\star\mathcal B)[U]を、第一成分U1U_1の大きさによって分類する。k=0,1,…,nk=0,1,\dots,nに対し

Pk={(U1,α,β)∈(A⋆B)[U] : ∣U1∣=k}P_k=\bigl\{(U_1,\alpha,\beta)\in(\mathcal A\star\mathcal B)[U]\ :\ |U_1|=k\bigr\}

と置くと、P0,…,PnP_0,\dots,P_nは互いに素であり、その合併は(A⋆B)[U](\mathcal A\star\mathcal B)[U]に等しい。

∣Pk∣|P_k|を求める。∣U1∣=k|U_1|=kを満たすU1⊆UU_1\subseteq Uは(nk)\binom nk個ある（§D2.2 命題 3.1）。U1U_1を一つ固定すると、α\alphaの取り方は∣A[U1]∣=ak|\mathcal A[U_1]|=a_k通り、β\betaの取り方は∣B[U∖U1]∣=bn−k|\mathcal B[U\setminus U_1]|=b_{n-k}通りである（命題 2.2）。U1U_1を固定したときの三つ組の個数は乗法原理（§D2.2 定理 2.3）によりakbn−ka_kb_{n-k}であり、U1U_1ごとの集合は互いに素であるから、加法原理（§D2.2 定理 2.1）により

∣Pk∣=(nk)akbn−k|P_k|=\binom nk a_kb_{n-k}

である。ふたたび加法原理により

∣(A⋆B)[U]∣=∑k=0n(nk)akbn−k\bigl|(\mathcal A\star\mathcal B)[U]\bigr|=\sum_{k=0}^{n}\binom nk a_kb_{n-k}

となる。命題 3.1により右辺はn! [xn](A^B^)n!\,[x^{n}](\widehat A\widehat B)に等しい。定義 2.3により左辺はn! [xn]A⋆B^n!\,[x^{n}]\widehat{\mathcal A\star\mathcal B}に等しい。nnは任意であったから、二つの形式的冪級数は係数がすべて一致し、等しい。▨

定理 5.2.B[∅]=∅\mathcal B[\emptyset]=\emptysetを満たすラベル付き組合せクラスB\mathcal Bに対し、[x0]B^=0[x^{0}]\widehat B=0であり、

Seq⁡(B)^(x)=11−B^(x)\widehat{\operatorname{Seq}(\mathcal B)}(x)=\frac{1}{1-\widehat B(x)}

が成り立つ。ここで右辺は補題 1.3 (3)により得られる1−B^1-\widehat Bの逆元である。

証明.b0=∣B[∅]∣=0b_0=|\mathcal B[\emptyset]|=0であるから[x0]B^=b0/0!=0[x^{0}]\widehat B=b_0/0!=0である。

各k≥0k\ge0に対しSeq⁡k(B)\operatorname{Seq}_k(\mathcal B)は定義 2.1の三条件を満たす。定義 2.1 条件 (a)と定義 2.1 条件 (b)は命題 4.4の証明と同じであり、有限性はSeq⁡(B)[U]\operatorname{Seq}(\mathcal B)[U]の部分集合であることによる。その母関数をS^k\widehat S_kと書く。

主張。各k≥0k\ge0に対しS^k=B^k\widehat S_k=\widehat B^{k}である。

kkについての帰納法で示す。k=0k=0のとき、Seq⁡0(B)[U]\operatorname{Seq}_0(\mathcal B)[U]は空列だけからなるが、成分の合併がUUに等しいという条件からU=∅U=\emptysetでなければならない。ゆえに計数列は1,0,0,…1,0,0,\dotsでありS^0=1=B^0\widehat S_0=1=\widehat B^{0}である。

k≥1k\ge1とし、k−1k-1について主張が成り立つとする。写像

Ψ ⁣:Seq⁡k(B)[U]⟶(B⋆Seq⁡k−1(B))[U],Ψ((U1,β1),…,(Uk,βk))=(U1, β1, ((U2,β2),…,(Uk,βk)))\Psi\colon\operatorname{Seq}_k(\mathcal B)[U]\longrightarrow\bigl(\mathcal B\star\operatorname{Seq}_{k-1}(\mathcal B)\bigr)[U],\qquad \Psi\bigl((U_1,\beta_1),\dots,(U_k,\beta_k)\bigr)=\Bigl(U_1,\ \beta_1,\ \bigl((U_2,\beta_2),\dots,(U_k,\beta_k)\bigr)\Bigr)

を考える。U2,…,UkU_2,\dots,U_kは互いに素で合併がU∖U1U\setminus U_1に等しいので、右辺の第三成分はSeq⁡k−1(B)[U∖U1]\operatorname{Seq}_{k-1}(\mathcal B)[U\setminus U_1]の元であり、Ψ\Psiは行き先の集合へ値を取る。Ψ\Psiは逆写像

(U1,β1,((U2,β2),…,(Uk,βk)))⟼((U1,β1),(U2,β2),…,(Uk,βk))(U_1,\beta_1,\bigl((U_2,\beta_2),\dots,(U_k,\beta_k)\bigr))\longmapsto\bigl((U_1,\beta_1),(U_2,\beta_2),\dots,(U_k,\beta_k)\bigr)

をもつので全単射である。ゆえに全単射原理（§D2.2 命題 1.5）と定理 5.1、および帰納法の仮定により

S^k=B^⋅S^k−1=B^⋅B^k−1=B^k\widehat S_k=\widehat B\cdot\widehat S_{k-1}=\widehat B\cdot\widehat B^{k-1}=\widehat B^{k}

である。主張が示された。

U={1,…,n}U=\{1,\dots,n\}と置く。命題 4.4の証明で見たとおり、B[∅]=∅\mathcal B[\emptyset]=\emptysetにより成分の個数kkはnn以下である。したがって

Seq⁡(B)[U]=⨆k=0nSeq⁡k(B)[U]\operatorname{Seq}(\mathcal B)[U]=\bigsqcup_{k=0}^{n}\operatorname{Seq}_k(\mathcal B)[U]

は互いに素な有限個の集合の合併であり、加法原理（§D2.2 定理 2.1）により

n! [xn]Seq⁡(B)^=∑k=0n∣Seq⁡k(B)[U]∣=∑k=0nn! [xn]B^kn!\,[x^{n}]\widehat{\operatorname{Seq}(\mathcal B)}=\sum_{k=0}^{n}\bigl|\operatorname{Seq}_k(\mathcal B)[U]\bigr|=\sum_{k=0}^{n}n!\,[x^{n}]\widehat B^{k}

となる。n!n!で割ると、右辺は補題 1.3 (2)で定められる∑k≥0B^k\sum_{k\ge0}\widehat B^{k}の第nn係数である。nnは任意であったからSeq⁡(B)^=∑k≥0B^k\widehat{\operatorname{Seq}(\mathcal B)}=\sum_{k\ge0}\widehat B^{k}であり、補題 1.3 (3)によりこれは(1−B^)−1(1-\widehat B)^{-1}に等しい。▨

定理 5.3.B[∅]=∅\mathcal B[\emptyset]=\emptysetを満たすラベル付き組合せクラスB\mathcal Bに対し

Set⁡(B)^(x)=exp⁡(B^(x))\widehat{\operatorname{Set}(\mathcal B)}(x)=\exp\bigl(\widehat B(x)\bigr)

が成り立つ。右辺は定義 1.4で定められる形式的な指数である。

証明.k≥0k\ge0を固定し、成分の順序を忘れる写像

Θ ⁣:Seq⁡k(B)[U]⟶Set⁡k(B)[U],Θ((U1,β1),…,(Uk,βk))={(U1,β1),…,(Uk,βk)}\Theta\colon\operatorname{Seq}_k(\mathcal B)[U]\longrightarrow\operatorname{Set}_k(\mathcal B)[U],\qquad \Theta\bigl((U_1,\beta_1),\dots,(U_k,\beta_k)\bigr)=\bigl\{(U_1,\beta_1),\dots,(U_k,\beta_k)\bigr\}

を考える。B[∅]=∅\mathcal B[\emptyset]=\emptysetにより各UiU_iは空でなく、互いに素であるからU1,…,UkU_1,\dots,U_kは相異なる。よって右辺の集合はちょうどkk個の元をもち、Θ\Thetaは行き先の集合へ値を取る。Θ\Thetaは全射である。実際、Set⁡k(B)[U]\operatorname{Set}_k(\mathcal B)[U]の元のkk個の成分に任意の順序を与えれば原像が得られる。

Θ\Thetaの原像の大きさを求める。Set⁡k(B)[U]\operatorname{Set}_k(\mathcal B)[U]の元T={(U1,β1),…,(Uk,βk)}T=\{(U_1,\beta_1),\dots,(U_k,\beta_k)\}を固定すると、Θ−1(T)\Theta^{-1}(T)はTTのkk個の成分を並べた列の全体である。成分は相異なるので、相異なる並べ方は相異なる列を与え、その個数は§D2.2 命題 3.1によりk!k!である。原像の族はSeq⁡k(B)[U]\operatorname{Seq}_k(\mathcal B)[U]を互いに素に分割するので、加法原理（§D2.2 定理 2.1）により

∣Seq⁡k(B)[U]∣=k!⋅∣Set⁡k(B)[U]∣\bigl|\operatorname{Seq}_k(\mathcal B)[U]\bigr|=k!\cdot\bigl|\operatorname{Set}_k(\mathcal B)[U]\bigr|

である。Set⁡k(B)\operatorname{Set}_k(\mathcal B)も命題 4.4と同じ議論によりラベル付き組合せクラスであり、定理 5.2の証明の主張により∣Seq⁡k(B)[U]∣=n! [xn]B^k\bigl|\operatorname{Seq}_k(\mathcal B)[U]\bigr|=n!\,[x^{n}]\widehat B^{k}（n=∣U∣n=|U|）であるから、Set⁡k(B)\operatorname{Set}_k(\mathcal B)の母関数はB^k/k!\widehat B^{k}/k!である。

U={1,…,n}U=\{1,\dots,n\}と置く。列の場合と同じ理由で成分の個数kkはnn以下であり、

Set⁡(B)[U]=⨆k=0nSet⁡k(B)[U]\operatorname{Set}(\mathcal B)[U]=\bigsqcup_{k=0}^{n}\operatorname{Set}_k(\mathcal B)[U]

であるから、加法原理により

[xn]Set⁡(B)^=∑k=0n1k![xn]B^k[x^{n}]\widehat{\operatorname{Set}(\mathcal B)}=\sum_{k=0}^{n}\frac{1}{k!}[x^{n}]\widehat B^{k}

となる。右辺は補題 1.3 (2)によりexp⁡(B^)\exp(\widehat B)の第nn係数である。nnは任意であったから主張を得る。▨

注意 5.4.定理 5.2と定理 5.3の仮定B[∅]=∅\mathcal B[\emptyset]=\emptysetは落とすことができない。B[∅]≠∅\mathcal B[\emptyset]\ne\emptysetならば、∅\emptysetをラベル集合とするB\mathcal B-対象β0\beta_0が存在し、U=∅U=\emptysetに対して長さkkの列((∅,β0),…,(∅,β0))((\emptyset,\beta_0),\dots,(\emptyset,\beta_0))がすべてのk≥0k\ge0について定まる。この場合Seq⁡(B)[∅]\operatorname{Seq}(\mathcal B)[\emptyset]は無限集合となり、定義 2.1 条件 (c)を満たさない。母関数の側でも、[x0]B^≠0[x^{0}]\widehat B\ne0のとき1−B^1-\widehat Bの定数項が零になることがあり、そのときは逆元が存在しない。

6 具体例

例 6.1.例 2.4の巡回順序のクラスC\mathcal Cに集合の構成を適用する。Set⁡(C)[U]\operatorname{Set}(\mathcal C)[U]の対象は、UUの分割の各ブロックに巡回順序を与えたものであり、これはUUの置換の巡回置換分解にほかならない。UUの置換は分解によってこの形の対象を一意に定め、逆にこの形の対象は置換を一意に定めるので、Set⁡(C)\operatorname{Set}(\mathcal C)の計数列はn!n!である。定理 5.3により

exp⁡(∑n≥1xnn)=∑n≥0xn\exp\left(\sum_{n\ge1}\frac{x^{n}}{n}\right)=\sum_{n\ge0}x^{n}

が形式的冪級数の等式として従う。

検算.C^=x+12x2+13x3+14x4+⋯\widehat C=x+\tfrac12x^{2}+\tfrac13x^{3}+\tfrac14x^{4}+\cdotsとする。C^2\widehat C^{2}の第2,3,42,3,4係数は順に11、2⋅1⋅12=12\cdot1\cdot\tfrac12=1、2⋅1⋅13+(12)2=23+14=11122\cdot1\cdot\tfrac13+\left(\tfrac12\right)^{2}=\tfrac23+\tfrac14=\tfrac{11}{12}である。C^3\widehat C^{3}の第3,43,4係数は11と3⋅1⋅1⋅12=323\cdot1\cdot1\cdot\tfrac12=\tfrac32、C^4\widehat C^{4}の第44係数は11である。ゆえにexp⁡(C^)=1+C^+12C^2+16C^3+124C^4+⋯\exp(\widehat C)=1+\widehat C+\tfrac12\widehat C^{2}+\tfrac16\widehat C^{3}+\tfrac1{24}\widehat C^{4}+\cdotsの係数は

[x1]=1,[x2]=12+12=1,[x3]=13+12+16=1,[x4]=14+12⋅1112+16⋅32+124=6+11+6+124=1[x^{1}]=1,\quad [x^{2}]=\tfrac12+\tfrac12=1,\quad [x^{3}]=\tfrac13+\tfrac12+\tfrac16=1,\quad [x^{4}]=\tfrac14+\tfrac12\cdot\tfrac{11}{12}+\tfrac16\cdot\tfrac32+\tfrac1{24}=\tfrac{6+11+6+1}{24}=1

となり、いずれもn!/n!=1n!/n!=1に一致する。

例 6.2.例 2.4の単一対象のクラスE\mathcal Eに集合の構成を適用する。Set⁡(E)[U]\operatorname{Set}(\mathcal E)[U]の対象はUUの分割そのものであり、その個数をBnB_nと書く。定理 5.3により

∑n≥0Bnn!xn=exp⁡(exp⁡(x)−1)\sum_{n\ge0}\frac{B_n}{n!}x^{n}=\exp\bigl(\exp(x)-1\bigr)

である。

検算.u=exp⁡(x)−1=x+12x2+16x3+124x4+⋯u=\exp(x)-1=x+\tfrac12x^{2}+\tfrac16x^{3}+\tfrac1{24}x^{4}+\cdotsと置く。u2u^{2}の第2,3,42,3,4係数は11、2⋅1⋅12=12\cdot1\cdot\tfrac12=1、2⋅1⋅16+(12)2=13+14=7122\cdot1\cdot\tfrac16+\left(\tfrac12\right)^{2}=\tfrac13+\tfrac14=\tfrac7{12}である。u3u^{3}の第3,43,4係数は11と3⋅1⋅1⋅12=323\cdot1\cdot1\cdot\tfrac12=\tfrac32、u4u^{4}の第44係数は11である。ゆえに

[x1]exp⁡(u)=1,[x2]exp⁡(u)=12+12=1,[x3]exp⁡(u)=16+12+16=56,[x4]exp⁡(u)=124+12⋅712+16⋅32+124=1+7+6+124=58[x^{1}]\exp(u)=1,\quad [x^{2}]\exp(u)=\tfrac12+\tfrac12=1,\quad [x^{3}]\exp(u)=\tfrac16+\tfrac12+\tfrac16=\tfrac56,\quad [x^{4}]\exp(u)=\tfrac1{24}+\tfrac12\cdot\tfrac7{12}+\tfrac16\cdot\tfrac32+\tfrac1{24}=\tfrac{1+7+6+1}{24}=\tfrac58

であり、Bn=n! [xn]exp⁡(u)B_n=n!\,[x^{n}]\exp(u)からB1=1B_1=1、B2=2B_2=2、B3=6⋅56=5B_3=6\cdot\tfrac56=5、B4=24⋅58=15B_4=24\cdot\tfrac58=15を得る。直接に数えると、{1,2,3}\{1,2,3\}の分割は{123}\{123\}、{1}{23}\{1\}\{23\}、{2}{13}\{2\}\{13\}、{3}{12}\{3\}\{12\}、{1}{2}{3}\{1\}\{2\}\{3\}の55個であり、{1,2,3,4}\{1,2,3,4\}の分割はブロックの大きさの型ごとに1+4+3+6+1=151+4+3+6+1=15個であって、いずれも一致する。

例 6.3.例 2.4の単一対象のクラスE\mathcal Eに列の構成を適用する。Seq⁡(E)[U]\operatorname{Seq}(\mathcal E)[U]の対象はUUの分割にブロックの順序を与えたものであり、その個数をFnF_nと書く。定理 5.2により

∑n≥0Fnn!xn=11−(exp⁡(x)−1)=12−exp⁡(x)\sum_{n\ge0}\frac{F_n}{n!}x^{n}=\frac{1}{1-(\exp(x)-1)}=\frac{1}{2-\exp(x)}

である。

検算.u=exp⁡(x)−1u=\exp(x)-1に対し∑k≥0uk\sum_{k\ge0}u^{k}の第33係数は、上の計算によりuuから16\tfrac16、u2u^{2}から11、u3u^{3}から11を受け取り、16+1+1=136\tfrac16+1+1=\tfrac{13}{6}である。ゆえにF3=6⋅136=13F_3=6\cdot\tfrac{13}{6}=13である。同じく第22係数は12+1=32\tfrac12+1=\tfrac32でありF2=2⋅32=3F_2=2\cdot\tfrac32=3である。直接に数えると、{1,2}\{1,2\}の順序づけられた分割は({12})(\{12\})、({1},{2})(\{1\},\{2\})、({2},{1})(\{2\},\{1\})の33個である。{1,2,3}\{1,2,3\}については、ブロックが一つのものが11個、二つのものが3⋅2=63\cdot2=6個、三つのものが3!=63!=6個で合計1313個であり、一致する。

注意 6.4. 列と集合の構成則は、本記事では大きさが零の対象をもたないクラスに対してだけ主張した。係数体は有理数体に固定し、収束は一切問わなかった。ラベル付き構造の巡回的な構成、複数の変数による重み付け、および母関数の解析的な漸近評価は扱っていない。

7 演習

問題 7.1.

  1. 例 2.4の線形順序のクラスL\mathcal Lについて、L⋆L\mathcal L\star\mathcal Lの計数列の第nn項が(n+1)!(n+1)!であることを、定理 5.1によって指数型母関数を求めて証明せよ。さらに、U={1,…,n}U=\{1,\dots,n\}に対し、(L⋆L)[U](\mathcal L\star\mathcal L)[U]から{1,…,n+1}\{1,\dots,n+1\}上の全順序の全体への全単射を一つ構成せよ。
  2. 定理 5.2の証明の主張（S^k=B^k\widehat S_k=\widehat B^{k}）を、先頭の成分を切り離すかわりに末尾の成分を切り離す全単射を用いて証明せよ。用いる全単射を明示し、定理 5.1のどちらの因子へB\mathcal Bを置くかを述べよ。
  3. 定理 5.3の証明で、Θ\Thetaの原像がちょうどk!k!個の元をもつことを示すために、成分のラベル集合が空でなく互いに素であることを用いた。B[∅]≠∅\mathcal B[\emptyset]\ne\emptysetを許した場合に、この段階が破れる具体例を一つ構成せよ。
  4. B∈Q[[x]]B\in\Q[[x]]を[x0]B=0[x^{0}]B=0を満たす元とし、整数m≥1m\ge1に対しSm=∑k≥0(k+m−1m−1)BkS_m=\sum_{k\ge0}\binom{k+m-1}{m-1}B^{k}と置く（補題 1.3 (2)により定まる）。(1−B)mSm=1(1-B)^{m}S_m=1を証明せよ。さらに、定数項が零でないBBに対して(1−B)∑k≥0Bk=1(1-B)\sum_{k\ge0}B^{k}=1という等式の左辺が定義されない理由を述べよ。
  5. 空でない各ラベル集合UUに対しB[U]\mathcal B[U]が二つの元からなるクラスB\mathcal Bを考える。B^\widehat Bを求め、Seq⁡(B)\operatorname{Seq}(\mathcal B)とSet⁡(B)\operatorname{Set}(\mathcal B)の計数列の第33項を、構成則から求めた値と直接の数え上げの双方で計算して一致を確かめよ。
  6. 定理 5.1を用いて、大きさnnの対象の個数が∑k=0n(nk)k!\sum_{k=0}^{n}\binom nk k!であるようなラベル付き組合せクラスを一つ構成し、その指数型母関数がexp⁡(x)/(1−x)\exp(x)/(1-x)に等しいことを証明せよ。
解答.

(1)を示す。例 2.4によりL^(x)=∑n≥0xn\widehat L(x)=\sum_{n\ge0}x^{n}である。定理 5.1によりL⋆L\mathcal L\star\mathcal Lの指数型母関数はL^2\widehat L^{2}であり、Cauchy 積の定義（§D2.4 定義 4.1）により

[xn]L^2=∑k=0n([xk]L^)([xn−k]L^)=∑k=0n1=n+1[x^{n}]\widehat L^{2}=\sum_{k=0}^{n}\bigl([x^{k}]\widehat L\bigr)\bigl([x^{n-k}]\widehat L\bigr)=\sum_{k=0}^{n}1=n+1

である。定義 2.3により、L⋆L\mathcal L\star\mathcal Lの計数列の第nn項はn! [xn]L^2=n! (n+1)=(n+1)!n!\,[x^{n}]\widehat L^{2}=n!\,(n+1)=(n+1)!である。命題 3.1の形で書くと、この等式は∑k=0n(nk)k! (n−k)!=∑k=0nn!=(n+1)!\sum_{k=0}^{n}\binom nk k!\,(n-k)!=\sum_{k=0}^{n}n!=(n+1)!である。

全単射を構成する。例 2.4で述べたとおり、有限集合VV上の全順序は、VVの元を小さい順に一度ずつ並べた語と一対一に対応する。以下、全順序をこの語と同一視する。定義 4.1により、(L⋆L)[U](\mathcal L\star\mathcal L)[U]の元は、部分集合U1⊆UU_1\subseteq Uと、U1U_1上の語w1w_1と、U∖U1U\setminus U_1上の語w2w_2の三つ組(U1,w1,w2)(U_1,w_1,w_2)である。この三つ組に、語w1w_1、文字n+1n+1、語w2w_2をこの順につないだ語

Θ(U1,w1,w2)=w1 (n+1) w2\Theta(U_1,w_1,w_2)=w_1\,(n+1)\,w_2

を対応させる。w1w_1の文字の集合U1U_1とw2w_2の文字の集合U∖U1U\setminus U_1は互いに素で合併がUUであり、n+1∉Un+1\notin Uであるから、Θ(U1,w1,w2)\Theta(U_1,w_1,w_2)は{1,…,n+1}\{1,\dots,n+1\}の各元をちょうど一度ずつ含む語、すなわち{1,…,n+1}\{1,\dots,n+1\}上の全順序である。逆向きの写像を定める。{1,…,n+1}\{1,\dots,n+1\}上の語wwの中で文字n+1n+1が現れる位置はただ一つである。その位置より前の部分語をw1w_1、後の部分語をw2w_2とし、w1w_1の文字の集合をU1U_1とする。U1⊆UU_1\subseteq Uであり、w2w_2の文字の集合はU∖U1U\setminus U_1であるから、(U1,w1,w2)(U_1,w_1,w_2)は(L⋆L)[U](\mathcal L\star\mathcal L)[U]の元である。Θ(U1,w1,w2)\Theta(U_1,w_1,w_2)の中で文字n+1n+1の前にある部分語はw1w_1、後にある部分語はw2w_2であるから、Θ\Thetaの後に逆向きの写像を施すともとの三つ組に戻る。wwを文字n+1n+1の位置で切り分けてからつなぎ直すとwwに戻るから、逆向きの写像の後にΘ\Thetaを施すともとの語に戻る。ゆえにΘ\Thetaは全単射である。全単射原理（§D2.2 命題 1.5）と§D2.2 命題 3.1により、∣(L⋆L)[U]∣\bigl|(\mathcal L\star\mathcal L)[U]\bigr|は{1,…,n+1}\{1,\dots,n+1\}の元の並べ方の個数(n+1)!(n+1)!に等しく、母関数から求めた値と一致する。さらに、∣U1∣=k|U_1|=kを満たす三つ組は、文字n+1n+1が第k+1k+1文字である語に送られる。そのような語は残りのnn文字の並べ方だけあるのでn!n!個であり、畳み込みの第kk項(nk)k! (n−k)!=n!\binom nk k!\,(n-k)!=n!に一致する。

(2)を示す。kkについての帰納法による。k=0k=0のとき、Seq⁡0(B)[U]\operatorname{Seq}_0(\mathcal B)[U]の元は空列だけであり、成分の合併がUUに等しいという条件からU=∅U=\emptysetでなければならない。ゆえに計数列は1,0,0,…1,0,0,\dotsであり、S^0=1=B^0\widehat S_0=1=\widehat B^{0}である。

k≥1k\ge1とし、S^k−1=B^k−1\widehat S_{k-1}=\widehat B^{k-1}が成り立つとする。定理 5.1の第一因子にSeq⁡k−1(B)\operatorname{Seq}_{k-1}(\mathcal B)を置き、第二因子にB\mathcal Bを置く。Seq⁡k−1(B)\operatorname{Seq}_{k-1}(\mathcal B)は、定理 5.2の証明で述べたとおりラベル付き組合せクラスである。正の整数からなる有限集合UUに対し、写像

Ψ′ ⁣:Seq⁡k(B)[U]⟶(Seq⁡k−1(B)⋆B)[U],Ψ′((U1,β1),…,(Uk,βk))=(U∖Uk, ((U1,β1),…,(Uk−1,βk−1)), βk)\Psi'\colon\operatorname{Seq}_k(\mathcal B)[U]\longrightarrow\bigl(\operatorname{Seq}_{k-1}(\mathcal B)\star\mathcal B\bigr)[U],\qquad \Psi'\bigl((U_1,\beta_1),\dots,(U_k,\beta_k)\bigr)=\Bigl(U\setminus U_k,\ \bigl((U_1,\beta_1),\dots,(U_{k-1},\beta_{k-1})\bigr),\ \beta_k\Bigr)

を考える。U1,…,UkU_1,\dots,U_kは互いに素で合併がUUに等しいので、U1,…,Uk−1U_1,\dots,U_{k-1}は互いに素で合併がU∖UkU\setminus U_kに等しい。したがって第二成分はSeq⁡k−1(B)[U∖Uk]\operatorname{Seq}_{k-1}(\mathcal B)[U\setminus U_k]の元である。またUk⊆UU_k\subseteq UであるからU∖(U∖Uk)=UkU\setminus(U\setminus U_k)=U_kであり、第三成分βk\beta_kはB[U∖(U∖Uk)]\mathcal B[U\setminus(U\setminus U_k)]の元である。ゆえに、定義 4.1によりΨ′\Psi'は行き先の集合へ値を取る。

逆向きの写像

(W, ((V1,γ1),…,(Vk−1,γk−1)), γ)⟼((V1,γ1),…,(Vk−1,γk−1),(U∖W,γ))\Bigl(W,\ \bigl((V_1,\gamma_1),\dots,(V_{k-1},\gamma_{k-1})\bigr),\ \gamma\Bigr)\longmapsto\bigl((V_1,\gamma_1),\dots,(V_{k-1},\gamma_{k-1}),(U\setminus W,\gamma)\bigr)

を考える。V1,…,Vk−1V_1,\dots,V_{k-1}は互いに素で合併がWWに等しく、U∖WU\setminus WはWWと交わらず、W∪(U∖W)=UW\cup(U\setminus W)=Uである。さらにγ∈B[U∖W]\gamma\in\mathcal B[U\setminus W]であるから、右辺はSeq⁡k(B)[U]\operatorname{Seq}_k(\mathcal B)[U]の元である。Ψ′\Psi'の後にこの写像を施すと、最後の成分は(U∖(U∖Uk),βk)=(Uk,βk)(U\setminus(U\setminus U_k),\beta_k)=(U_k,\beta_k)となり、もとの列に戻る。この写像の後にΨ′\Psi'を施すと、第一成分はU∖(U∖W)=WU\setminus(U\setminus W)=Wとなり、もとの三つ組に戻る。ここでW⊆UW\subseteq Uを用いた。ゆえにΨ′\Psi'は全単射である。

U={1,…,n}U=\{1,\dots,n\}として全単射原理（§D2.2 命題 1.5）を用いると、Seq⁡k(B)\operatorname{Seq}_k(\mathcal B)とSeq⁡k−1(B)⋆B\operatorname{Seq}_{k-1}(\mathcal B)\star\mathcal Bの計数列は一致する。定理 5.1と帰納法の仮定により

S^k=S^k−1⋅B^=B^k−1⋅B^\widehat S_k=\widehat S_{k-1}\cdot\widehat B=\widehat B^{k-1}\cdot\widehat B

である。命題 1.2 (2)によりB^k−1B^=B^ B^k−1=B^k\widehat B^{k-1}\widehat B=\widehat B\,\widehat B^{k-1}=\widehat B^{k}であるから、S^k=B^k\widehat S_k=\widehat B^{k}である。

(3)の例として、B[∅]={∗}\mathcal B[\emptyset]=\{\ast\}とし、空でないUUに対してB[U]={U}\mathcal B[U]=\{U\}と定める。全単射σ ⁣:U→V\sigma\colon U\to Vに対し、B[σ]\mathcal B[\sigma]を、U=∅U=\emptysetのとき∗↦∗\ast\mapsto\ast、U≠∅U\ne\emptysetのときU↦VU\mapsto Vと定める。各B[U]\mathcal B[U]は要素が一つの集合であり、要素が一つの集合の間の写像はただ一つであるから、定義 2.1 条件 (a)と定義 2.1 条件 (b)の両辺は一致する。定義 2.1 条件 (c)も成り立つ。ゆえにB\mathcal BはB[∅]≠∅\mathcal B[\emptyset]\ne\emptysetを満たすラベル付き組合せクラスである。

U={1}U=\{1\}、k=3k=3とする。Seq⁡3(B)[U]\operatorname{Seq}_3(\mathcal B)[U]の元((U1,β1),(U2,β2),(U3,β3))\bigl((U_1,\beta_1),(U_2,\beta_2),(U_3,\beta_3)\bigr)では、U1,U2,U3U_1,U_2,U_3は互いに素なUUの部分集合で合併が{1}\{1\}であるから、ちょうど一つのiiについてUi={1}U_i=\{1\}であり、残りの二つは∅\emptysetである。各βi\beta_iはB[Ui]\mathcal B[U_i]のただ一つの元に定まるので、Seq⁡3(B)[U]\operatorname{Seq}_3(\mathcal B)[U]は

s1=(({1},{1}),(∅,∗),(∅,∗)),s2=((∅,∗),({1},{1}),(∅,∗)),s3=((∅,∗),(∅,∗),({1},{1}))s_1=\bigl((\{1\},\{1\}),(\emptyset,\ast),(\emptyset,\ast)\bigr),\quad s_2=\bigl((\emptyset,\ast),(\{1\},\{1\}),(\emptyset,\ast)\bigr),\quad s_3=\bigl((\emptyset,\ast),(\emptyset,\ast),(\{1\},\{1\})\bigr)

の三つの元からなる。成分の順序を忘れる対応は、s1,s2,s3s_1,s_2,s_3をいずれも集合T={({1},{1}),(∅,∗)}T=\bigl\{(\{1\},\{1\}),(\emptyset,\ast)\bigr\}へ送る。二つの成分のラベル集合がともに∅\emptysetであり、互いに素であっても相異なるとは限らないので、TTの元は33個ではなく22個である。したがって、定理 5.3の証明のうち、U1,…,UkU_1,\dots,U_kが相異なり、像の集合がちょうどkk個の元をもつという段階が破れる。さらに、TTへ送られる列はs1,s2,s3s_1,s_2,s_3の33個であり、原像の大きさは3!=63!=6ではない。∣Seq⁡3(B)[U]∣=3\bigl|\operatorname{Seq}_3(\mathcal B)[U]\bigr|=3は3!3!で割り切れないので、∣Seq⁡3(B)[U]∣\bigl|\operatorname{Seq}_3(\mathcal B)[U]\bigr|を3!3!と整数の積として表す等式は成り立たない。

(4)の前半を示す。まず、有理数の列(λk)k≥0(\lambda_k)_{k\ge0}とΛ=∑k≥0λkBk\Lambda=\sum_{k\ge0}\lambda_kB^{k}に対し、μ0=0\mu_0=0、μk=λk−1\mu_k=\lambda_{k-1}（k≥1k\ge1）と置くと

BΛ=∑k≥0μkBkB\Lambda=\sum_{k\ge0}\mu_kB^{k}

が成り立つことを示す。右辺は補題 1.3 (2)により定まる。n≥0n\ge0を固定する。Cauchy 積の定義（§D2.4 定義 4.1）により[xn](BΛ)=∑j=0n([xj]B)([xn−j]Λ)[x^{n}](B\Lambda)=\sum_{j=0}^{n}([x^{j}]B)([x^{n-j}]\Lambda)である。1≤j≤n1\le j\le nの項では、補題 1.3 (2)の定義により[xn−j]Λ=∑k=0n−jλk[xn−j]Bk[x^{n-j}]\Lambda=\sum_{k=0}^{n-j}\lambda_k[x^{n-j}]B^{k}であり、n−j<k≤n−1n-j<k\le n-1を満たすkkについては補題 1.3 (1)により[xn−j]Bk=0[x^{n-j}]B^{k}=0であるから、[xn−j]Λ=∑k=0n−1λk[xn−j]Bk[x^{n-j}]\Lambda=\sum_{k=0}^{n-1}\lambda_k[x^{n-j}]B^{k}である。j=0j=0の項は、[x0]B=0[x^{0}]B=0により、[xn]Λ[x^{n}]\Lambdaのかわりに∑k=0n−1λk[xn]Bk\sum_{k=0}^{n-1}\lambda_k[x^{n}]B^{k}を掛けても00のままである。ゆえに、有限和の順序を交換し、Cauchy 積の定義とBk+1=B BkB^{k+1}=B\,B^{k}を用いると

[xn](BΛ)=∑k=0n−1λk∑j=0n([xj]B)([xn−j]Bk)=∑k=0n−1λk[xn]Bk+1=∑k=1nμk[xn]Bk[x^{n}](B\Lambda)=\sum_{k=0}^{n-1}\lambda_k\sum_{j=0}^{n}\bigl([x^{j}]B\bigr)\bigl([x^{n-j}]B^{k}\bigr)=\sum_{k=0}^{n-1}\lambda_k[x^{n}]B^{k+1}=\sum_{k=1}^{n}\mu_k[x^{n}]B^{k}

である。μ0=0\mu_0=0であるから、右端は∑k=0nμk[xn]Bk=[xn]∑k≥0μkBk\sum_{k=0}^{n}\mu_k[x^{n}]B^{k}=[x^{n}]\sum_{k\ge0}\mu_kB^{k}に等しい。n=0n=0のとき両辺は00である。

次に、m≥1m\ge1について(1−B)Sm+1=Sm(1-B)S_{m+1}=S_mを示す。前段をλk=(k+mm)\lambda_k=\binom{k+m}{m}に適用すると、BSm+1=∑k≥0μkBkBS_{m+1}=\sum_{k\ge0}\mu_kB^{k}、μ0=0\mu_0=0、μk=(k+m−1m)\mu_k=\binom{k+m-1}{m}（k≥1k\ge1）である。補題 1.3 (2)の級数は係数ごとの有限和で定まるので、二つの級数∑k≥0λkBk\sum_{k\ge0}\lambda_kB^{k}と∑k≥0μkBk\sum_{k\ge0}\mu_kB^{k}の差は∑k≥0(λk−μk)Bk\sum_{k\ge0}(\lambda_k-\mu_k)B^{k}に等しい。k=0k=0のときλ0−μ0=(mm)=1=(m−1m−1)\lambda_0-\mu_0=\binom mm=1=\binom{m-1}{m-1}である。k≥1k\ge1のとき1≤m≤k+m−11\le m\le k+m-1であるから、パスカルの公式（§D2.2 命題 5.2）を(k+mm)\binom{k+m}{m}に用いると

λk−μk=(k+mm)−(k+m−1m)=(k+m−1m−1)\lambda_k-\mu_k=\binom{k+m}{m}-\binom{k+m-1}{m}=\binom{k+m-1}{m-1}

である。ゆえに(1−B)Sm+1=Sm+1−BSm+1=∑k≥0(k+m−1m−1)Bk=Sm(1-B)S_{m+1}=S_{m+1}-BS_{m+1}=\sum_{k\ge0}\binom{k+m-1}{m-1}B^{k}=S_mである。

最後に、(1−B)mSm=1(1-B)^{m}S_m=1をmmについての帰納法で示す。m=1m=1のときS1=∑k≥0BkS_1=\sum_{k\ge0}B^{k}であり、主張は補題 1.3 (3)である。m≥1m\ge1について主張が成り立つとすると、命題 1.2 (3)の結合性と前段により

(1−B)m+1Sm+1=(1−B)m((1−B)Sm+1)=(1−B)mSm=1(1-B)^{m+1}S_{m+1}=(1-B)^{m}\bigl((1-B)S_{m+1}\bigr)=(1-B)^{m}S_m=1

である。命題 1.2 (2)によりSm(1−B)m=1S_m(1-B)^{m}=1でもあるから、(1−B)m(1-B)^{m}は可逆元であり、その逆元はSmS_mである。とくにB=xB=xのとき、[xn]xk[x^{n}]x^{k}はk=nk=nのとき11、それ以外のとき00であるから[xn]Sm=(n+m−1m−1)[x^{n}]S_m=\binom{n+m-1}{m-1}であり、§D2.4 命題 5.2のα=1\alpha=1の場合をQ[[x]]\Q[[x]]において得る。

(4)の後半では、b0=[x0]B≠0b_0=[x^{0}]B\ne0とする。Cauchy 積の定義により、任意のF,G∈Q[[x]]F,G\in\Q[[x]]に対して[x0](FG)=([x0]F)([x0]G)[x^{0}](FG)=([x^{0}]F)([x^{0}]G)であるから、kkについての帰納法により[x0]Bk=b0k[x^{0}]B^{k}=b_0^{k}である。Q\Qは体でありb0≠0b_0\ne0であるから、すべてのk≥0k\ge0についてb0k≠0b_0^{k}\ne0である。したがって、∑k≥0Bk\sum_{k\ge0}B^{k}の第00係数を定めるには、00でない有理数b0kb_0^{k}を無限個足さなければならない。補題 1.3 (2)は、各係数が有限和になることによってだけ無限和∑k≥0λkBk\sum_{k\ge0}\lambda_kB^{k}を定めており、形式的冪級数の枠組みでは有理数の無限和の収束を考えない。ゆえにb0≠0b_0\ne0のとき∑k≥0Bk\sum_{k\ge0}B^{k}はQ[[x]]\Q[[x]]の元として定義されず、左辺(1−B)∑k≥0Bk(1-B)\sum_{k\ge0}B^{k}も定義されない。とくにb0=1b_0=1のときは、どのS∈Q[[x]]S\in\Q[[x]]についても[x0]((1−B)S)=(1−b0)[x0]S=0[x^{0}]\bigl((1-B)S\bigr)=(1-b_0)[x^{0}]S=0であるから、(1−B)S=1(1-B)S=1を満たすSSそのものが存在しない。

(5)では、Seq⁡(B)\operatorname{Seq}(\mathcal B)とSet⁡(B)\operatorname{Set}(\mathcal B)がB[∅]=∅\mathcal B[\emptyset]=\emptysetのときに定義されるので、B[∅]=∅\mathcal B[\emptyset]=\emptysetとする。たとえば、空でないUUに対してB[U]={(U,0),(U,1)}\mathcal B[U]=\{(U,0),(U,1)\}とし、全単射σ ⁣:U→V\sigma\colon U\to Vに対してB[σ](U,c)=(V,c)\mathcal B[\sigma](U,c)=(V,c)（c∈{0,1}c\in\{0,1\}）と定める。B[idU]\mathcal B[\mathrm{id}_U]は恒等写像であり、全単射σ ⁣:U→V\sigma\colon U\to V、τ ⁣:V→W\tau\colon V\to Wに対してB[τ∘σ](U,c)=(W,c)=B[τ](B[σ](U,c))\mathcal B[\tau\circ\sigma](U,c)=(W,c)=\mathcal B[\tau]\bigl(\mathcal B[\sigma](U,c)\bigr)であるから、B\mathcal Bはラベル付き組合せクラスである。以下の計算は∣B[U]∣|\mathcal B[U]|の値だけを用いる。計数列はb0=0b_0=0、bn=2b_n=2（n≥1n\ge1）であるから、例 2.4のE^(x)=exp⁡(x)−1\widehat E(x)=\exp(x)-1を用いて

B^(x)=∑n≥12n!xn=2(exp⁡(x)−1)\widehat B(x)=\sum_{n\ge1}\frac{2}{n!}x^{n}=2\bigl(\exp(x)-1\bigr)

である。

u=B^u=\widehat Bと置くと、[x1]u=2[x^{1}]u=2、[x2]u=1[x^{2}]u=1、[x3]u=13[x^{3}]u=\tfrac13である。Cauchy 積の定義と[x0]u=0[x^{0}]u=0により、[x3]u2=2⋅([x1]u)([x2]u)=4[x^{3}]u^{2}=2\cdot([x^{1}]u)([x^{2}]u)=4、[x3]u3=([x1]u)3=8[x^{3}]u^{3}=([x^{1}]u)^{3}=8である。補題 1.3 (1)によりk≥4k\ge4のとき[x3]uk=0[x^{3}]u^{k}=0であり、[x3]u0=0[x^{3}]u^{0}=0である。定理 5.2と定理 5.3により

3! [x3]Seq⁡(B)^=6(13+4+8)=74,3! [x3]Set⁡(B)^=6(13+42+86)=223!\,[x^{3}]\widehat{\operatorname{Seq}(\mathcal B)}=6\Bigl(\frac13+4+8\Bigr)=74,\qquad 3!\,[x^{3}]\widehat{\operatorname{Set}(\mathcal B)}=6\Bigl(\frac13+\frac42+\frac86\Bigr)=22

である。

直接に数える。U={1,2,3}U=\{1,2,3\}とする。Seq⁡(B)[U]\operatorname{Seq}(\mathcal B)[U]の元((U1,β1),…,(Uk,βk))\bigl((U_1,\beta_1),\dots,(U_k,\beta_k)\bigr)では、B[∅]=∅\mathcal B[\emptyset]=\emptysetにより各UiU_iは空でないので、(U1,…,Uk)(U_1,\dots,U_k)はUUの分割のブロックを一列に並べたものであり、各βi\beta_iの選び方は22通りである。ブロックを並べた列の個数は、k=1k=1のとき11、k=2k=2のとき空でない真部分集合U1U_1の個数66、k=3k=3のとき一元集合の並べ方の個数3!=63!=6である。乗法原理（§D2.2 定理 2.3）と加法原理（§D2.2 定理 2.1）により

∣Seq⁡(B)[U]∣=1⋅2+6⋅22+6⋅23=2+24+48=74\bigl|\operatorname{Seq}(\mathcal B)[U]\bigr|=1\cdot2+6\cdot2^{2}+6\cdot2^{3}=2+24+48=74

である。Set⁡(B)[U]\operatorname{Set}(\mathcal B)[U]の元はUUの分割の各ブロックにB\mathcal B-対象を与えたものである。UUの分割は、ブロックが一つのものが11個、二つのものが33個、三つのものが11個であるから

∣Set⁡(B)[U]∣=1⋅2+3⋅22+1⋅23=2+12+8=22\bigl|\operatorname{Set}(\mathcal B)[U]\bigr|=1\cdot2+3\cdot2^{2}+1\cdot2^{3}=2+12+8=22

である。いずれも構成則から求めた値と一致する。

(6)を示す。正の整数からなる各有限集合UU（U=∅U=\emptysetを含む）に対してE∘[U]={U}\mathcal E^{\circ}[U]=\{U\}とし、全単射σ ⁣:U→V\sigma\colon U\to Vに対してE∘[σ](U)=V\mathcal E^{\circ}[\sigma](U)=Vと定める。各E∘[U]\mathcal E^{\circ}[U]は要素が一つの集合であるから、定義 2.1の三条件が成り立ち、E∘\mathcal E^{\circ}はラベル付き組合せクラスである。計数列はすべてのn≥0n\ge0について11であるから、定義 1.4によりE∘^(x)=∑n≥0xn/n!=exp⁡(x)\widehat{E^{\circ}}(x)=\sum_{n\ge0}x^{n}/n!=\exp(x)である。

求めるクラスとしてL⋆E∘\mathcal L\star\mathcal E^{\circ}を取る。その対象(U1,≤,U∖U1)(U_1,\le,U\setminus U_1)は、部分集合U1⊆UU_1\subseteq UとU1U_1上の全順序≤\leの組と一対一に対応する。定義 2.3と定理 5.1と命題 3.1により、U={1,…,n}U=\{1,\dots,n\}に対して

∣(L⋆E∘)[U]∣=n! [xn](L^ E∘^)=∑k=0n(nk)ℓk⋅1=∑k=0n(nk)k!\bigl|(\mathcal L\star\mathcal E^{\circ})[U]\bigr|=n!\,[x^{n}]\bigl(\widehat L\,\widehat{E^{\circ}}\bigr)=\sum_{k=0}^{n}\binom nk\ell_k\cdot1=\sum_{k=0}^{n}\binom nk k!

である。ここで例 2.4のℓk=k!\ell_k=k!を用いた。同じ例のL^(x)=(1−x)−1\widehat L(x)=(1-x)^{-1}により、指数型母関数は

L⋆E∘^(x)=L^(x) E∘^(x)=(1−x)−1exp⁡(x)=exp⁡(x)1−x\widehat{\mathcal L\star\mathcal E^{\circ}}(x)=\widehat L(x)\,\widehat{E^{\circ}}(x)=(1-x)^{-1}\exp(x)=\frac{\exp(x)}{1-x}

である。▨

参考文献

  1. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.ラベル付き積、列および集合の構成則の定式化を参考にした。
  2. Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.指数型母関数と集合分割・置換の例を参考にした。
  3. Ivan Niven, Formal power series, The American Mathematical Monthly 76 (1969), no. 8, 871–889.形式的冪級数を収束と無関係に扱う枠組みを参考にした。

前提記事