§E13.1指数型母関数

証明. 以下$f_i=[x^{i}]F$、$g_j=[x^{j}]G$、$h_k=[x^{k}]H$と書く。

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

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

である。

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

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

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

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

(4)を示す。$R$の分配法則と有限和の分割により、各$n$について

である。

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

であり、$F\cdot1=F$である。(2)により$1\cdot F=F$でもある。

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

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

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

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

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

(3)を示す。$S=\sum_{k\ge0}B^{k}$と置く。$n$を固定すると、(1)により

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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