こんにちは。株式会社オプティマインドの伊豆原と申します。当社の競プロ部に所属しています。
競プロで出てくる数え上げ問題では、母関数を使うと見通しが良くなることがしばしばあります。私自身はあまり組合せ論が得意でなく母関数にも不慣れだったので、これはいかん！と思って最近は下記の本で勉強しています(以下、本)。
- Set Operads in Combinatorics and Computer Science(2015)
本記事では当社の競プロ部の活動の一環として勉強の振り返りも兼ねて、本の主題となっているCombinatorial Species(組合せ種？)の簡単な紹介をしたいと思います。
Combinatorial Speciesの定義
Combinatorial Speciesは母関数の背景構造を考えたようなもので、André Joyalによる下記の論文で提案されました(以下、原論文)。
- Une théorie combinatoire des séries formelles(1981)
Combinatorial Speciesの定義を述べます。$\mathbb{B}$を有限集合とその間の全単射からなる圏(つまりgroupoid)、$\mathbb{F}$を有限集合とその間の任意の写像からなる圏とした時、Combinatorial Speciesはその間の共変函手
R : \mathbb{B} \to \mathbb{F}
として定義されます。定義として簡潔過ぎる感じがありますが、つまりは$R$として集合$V$から"$V$を頂点集合とした単純グラフ全体の集合"とか"$V$の分割全体の集合"などの組合せ的な集合に対応させるものを念頭に置いている感じです。
集合$V$の対応先は$R[V]$と書かれます。特に、集合の個数だけに着目したい場合は$k$点集合の対応先を指して$R[k]$と書きます。また、函手の言葉で書いているだけあってSpecies間の写像を自然変換として考えることができます(このために値域は$\mathbb{B}$でなく$\mathbb{F}$が使用されています)。
Species$R$が与えられるとその母関数$R(x)$を考えることができます。数え上げの問題としては欲しいのはむしろ、この母関数の情報ですね。利便性のために指数型母関数がよく使用されます。
$$ R(x) := \sum_{k=0}^\infty \dfrac{|R[k]|}{n!} x^n$$
下記は集合から"その集合の要素を並べてできるリスト全体の集合"へ対応させるSpecies$\mathbb{L}$の$|V|=3$における例です。また$|\mathbb{L}[k]| = k!$となるため、母関数は$\mathbb{L}(x)=1+x+x^2+\cdots = \dfrac{1}{1-x}$となります。
Combinatorial Speciesの例
要するに集合に集合を対応させる函手がSpeciesなので、例としては大量に存在します。例えばリスト$\mathbb{L}$(集合の要素を1列に並べたもの)、サイクル$\mathbb{C}$(集合を円状に並べたもの)、置換$\mathbb{S}$(集合の置換全体)、単純無向グラフ$\mathscr{G}$、冪集合$\mathcal{P}$(集合の部分集合全体)、基点付き木$\mathscr{A}$などなど。
ここで注意なのは、2つのSpecies$H,R$に対して各$[n]$について$|R[n]|=|H[n]|$(つまり母関数が同じ)でも、Speciesとして同型になるとは限らない点です。例えばリスト$\mathbb{L}$と置換$\mathbb{S}$は母関数は同じですが、関数の作用の様子が異なるためSpeciesとして同型ではありません。例として集合$V=\{1,2,3\}$上の関数$f:1\mapsto 1, 2\mapsto3, 3\mapsto2$がリストと置換それぞれへの作用が異なる様子を図に表します。
Combinatorial Species上の演算
Speciesの間ではいろいろな演算を考えることができます。以下、代表的なものを紹介していきます。
和
シンプルに(非交な)和集合を取ったものが和の演算になります。
$$(H+R)[V] := H[V] \sqcup R[V]$$
この場合、母関数においても$(R+H)(x) = R(x) + H(x)$になります。また$H+0=0+H=H$となる単位元$0$が存在して以下になります。
$$ 0[V] := \emptyset \ (\forall V \in \mathbb{B})$$
積
集合を2つに分割し、それぞれにSpeciesを作用させた結果の直積が積になります。同じものの積ならば冪乗で書かれます。
$$(H.R)[V] := \bigsqcup_{V_1 \sqcup V_2 = V}(H[V_1]\times R[V_2])$$
母関数においても$R.H(x) = R(x)H(x)$が成立し、また$H.1=1.H=H$となる単位元$1$が存在して以下になります。
1[V] =
\begin{cases}
\{\emptyset\} & (V=\emptyset) \\
\emptyset & (\text{else}) \\
\end{cases}
下はリストとサイクルの積$\mathbb{L}.\mathbb{C}$による集合$\mathbb{L}.\mathbb{C}[4]$に含まれる要素の例になります(リストの関係を点線矢印、サイクルの関係を実矢印で表しています)。
他にも関連するSpeciesとして、集合$V$から"その集合を唯一の要素として含む集合$\{V\}$"へ対応させるSpecies$E$があります。これを考えると$E.H= H.E$は集合$V$から"部分集合$U\subseteq V$の$H$による対応先全体の集合"となります。
H.E[V]=E.H[V] = \bigsqcup_{U\subseteq V} H[U]
特に$E^2 = E.E \cong \mathcal{P}$(冪集合のSpecies)が言えますね。
代入
これが重要な操作です。まずSpecies$R$と$H$の母関数を考えますと、もちろん関数なので片方をもう片方に代入することができます。
$$ H(R(x)) = \sum_{k=0}^\infty |H[k]| \dfrac{(R(x))^k}{k!}$$
では母関数が$H(R)(x)=H(R(x))$となるような$H(R)$はどういうSpeciesになるでしょうか？$R$がpositive($\Leftrightarrow R[\emptyset]=\emptyset$)な場合、それが次で与えられます。
H(R)[V] = \bigsqcup_{\pi \in \Pi[V]} \big( \prod_{B\in \pi} R[B] \big)\times H[\pi]
ここで$\Pi$は分割、つまり集合から"その集合の分割全体"からなる集合へのSpeciesになります(積記号と見た目が被ってますが、まぁ混乱はしないでしょう。本ではちょっと斜めになってます)。例えば3点集合$\{ a,b,c\}$に対して分割は以下になります(簡潔のため$\{\{a,b\},\{c\}\}$を$(ab)(c)$などと略記してます)。
\Pi [ \{ a,b,c\}] = \{ (a)(b)(c),(ab)(c),(ac)(b),(a)(bc),(abc)\}
下図は単純無向グラフ$\mathscr{G}$による$\mathscr{G}(\mathscr{G})[6]$の要素の例です。構造が入れ子になっている感じですね。
下記のシングルトンと呼ばれるSpecies$X$を考えると$R(X)=X(R)=R$となります。単位元みたいなものですね。
X[V] =
\begin{cases}
V & (|V|=1) \\
\emptyset & (\text{else}) \\
\end{cases}
Species間の恒等式
積や代入を使うと、いろいろと面白いSpecies間の恒等式を構成することができます。ここでは本や原論文で紹介されているものの中からいくつか紹介します。
-
$\mathbb{L} = 1 + X + X^2 + X^3 + \cdots$ (本のExample 3.3)
$X^n$は積の定義から$|V|\neq n$の時は空で、$X[n]$は$n$個の要素を並べたもの全体の集合になります。なので無限和を取ればこれはリストになります。 -
$\Pi = E(E_+)$ (本のExample 3.9)
ここで$E_+$は$E$から空集合を除いたものになります(つまり$E=1+E_+$)。代入自体が分割を使用して定義されることから導かれる式ですが、ここから分割の母関数の等式$\Pi(x) = e^{e^x -1}$が導けます。Newton法により$N$次までが$\mathcal{O}(N \log N)$で求まりますね。 -
$\mathbb{S}=\mathbb{S}_0.E$ (原論文のExample 7)
ここで$\mathbb{S}_0$は固定点無しの置換全体の集合です。等式自体は自明ですが母関数を考えると$\dfrac{1}{1-x} = \mathbb{S}_0(x) e^x$となり、よって$\mathbb{S}_0(x) = \dfrac{e^{-x}}{1-x}$が言えます。 -
$\mathscr{A} = X.E(\mathscr{A})$ (本の3.2.5.2節)
基点付き木構造$\mathscr{A}$のimplicitな等式になります。木構造の最適的な性質が等式にも現れている形になります。
応用(Cayleyの公式の証明)
ここではSpeciesの応用例として、原論文で紹介されているCayleyの公式の証明について触れたいと思います。Cayleyの公式とは"$n$点のラベル付き頂点を持つ木の個数は$n^{n-2}$である"というものです。
- Cayleys' formula
これを証明するためにまずVertebrata(脊椎動物)というSpecies$\mathscr{V}$を紹介します。$\mathscr{V}$は2点(head, tail)付き木構造のSpeciesでして、つまり$\mathscr{V}[V]$は"集合$V$を頂点とする木から区別される2点を選んだもの"になります。脊椎動物という言葉はおそらくその意味するグラフの形から由来していると思われます。
さて上の図からも明らかなように、$\mathscr{V}$は基点付き木のSpecies$\mathscr{A}$を用いて次のように表されます。$\mathscr{A}^n$の乗数$n$が脊椎の長さに対応する感じです。
$$ \mathscr{V} = \mathscr{A} + \mathscr{A}^2 + \mathscr{A}^3 + \cdots $$
もうひとつのSpecies$\mathbb{D}$を紹介します。$\mathbb{D}$はEnd functions、つまり$\mathbb{D}[V]$が"$V$から$V$への写像全体の成す集合"となるSpeciesです。この時、次の等式が成り立ちます($\mathbb{S}$は置換のなすSpecies)。
$$ \mathbb{D} = \mathbb{S}(\mathscr{A})$$
これは$f \in \mathbb{D}[V]$それぞれから関数グラフと呼ばれる"いくつかのサイクル(1点含む)とその各点を基点とした木からなるグラフ"が構成され、代入の定義である$\mathbb{S}(\mathscr{A})[V] = \bigsqcup_{\pi \in \Pi[V]} \big( \prod_{B\in \pi} \mathbb{A}[B] \big)\times \mathbb{S}[\pi]$と比較すると$\mathbb{S}[\pi]$がサイクル部分、$\mathscr{A}[B]$が木の部分に対応することから分かります。
ではここで、$n$点からなるラベル付き木の個数$a_n$を求めてみましょう。まず、木から2点選ぶ通り数は$n^2$であるため、脊髄動物のSpeciesの関連として$|\mathscr{V}[n]| = n^2 a_n$であることが分かります。 また定義から$|\mathbb{D}[n]| = n^n$であり、かつ$\mathbb{D}$と$\mathscr{V}$の母関数を比較すると
$$ \mathscr{V}(x) = \sum_{k=1}^\infty \mathscr{A}(x)^k = \mathbb{S}(\mathscr{A})(x)-1 = \mathbb{D}(x)-1$$
となるため、$n \geq 1$において$|\mathscr{V}[n]|=|\mathbb{D}[n]|$であることが分かります。よって$n^2 a_n = n^n$となり、Cayleyの公式$a_n = n^{n-2}$が導かれます。シンプルですね。
Operad構造
最後に、冒頭に紹介した本"Set Operads in Combinatorics and Computer Science"で扱われ、タイトルにも含まれているOperadついて紹介します。
Speciesの成す圏のモノイド対象としてOperadが定義できます。つまりpositiveなSpecies$\mathcal{O}$に対して2つの写像
\mu : \mathcal{O}(\mathcal{O}) \to \mathcal{O} \\
\eta : X \to \mathcal{O}
が存在し、単位則や結合則を満たすときに$\mathcal{O}$をOperadと呼びます。
Operadの例としては非空な単純グラフ$\mathscr{G}_+$があります。演算$\mu$としては例えば下図のように、分割の要素間が辺で繋がれている時にその分割の要素内の頂点すべてを互いに繋ぐ、などで構成できます(下図赤線が$\mu$によって追加された辺です)。
Operad構造があると何ができるかと言うと、つまりは演算が定義できるので、その演算に関して"cancellable"なOperadとか、あるいは具体的な$\mathcal{O}[V]$の中で"prime"な要素や整除関係などを考えることができます。本の3.3.2節あるいは同著者の下記の論文では、値域を通常の有限集合からposetに変えたMöbius Speciesを提案し、代入操作に関する"逆元"$\mathcal{O}^{<-1>}$(つまり$\mathcal{O}(\mathcal{O}^{<-1>}(x)) = \mathcal{O}^{<-1>}(\mathcal{O}(x)) = x$となるような$\mathcal{O}^{<-1>}$を作り上げています。
節4.5.1ではこの逆元を使用した次のような等式が紹介されています。ここで$\mathscr{D}_+$は有向グラフ(から空集合を除いたもの)のSpeciesで、$\mathcal{P}_{\mathscr{D}_+}$は$\mathscr{D}_+$の中でprimeな(つまり$\mu$の像に入ってないような)要素全体の集合によるSpeciesです。3次の係数が26なのは、つまり頂点が3つでprimeな有向グラフは26種類であることを示しています。
\begin{align}
\mathcal{P}_{\mathscr{D}_+} &= -\mathscr{D}_+^{<+1>}(x) - 2x + 2 \log(1+x) + \dfrac{1}{1+x} \\
&= 26 \dfrac{x^3}{3!} + 2460 \dfrac{x^4}{4!} + 842664 \dfrac{x^5}{5!} + 990642240 \dfrac{x^6}{6!}
\end{align}
下図は本のFig 4.4をそのまま写したものですが、確かに6+6+6+6+2=26個ありますね。豊かな構造は豊かな等式を生むようです。
まとめ
以上、Combinatorial Speciesについて簡単に紹介させて頂きました。素朴な定義から豊かな理論が構築されるのはかなり理想的に感じますね。引き続き学習や調査を進め、まとまった理解を得れましたらまた記事などにしていきたいと思います。
読んで頂きありがとうございました！