組合せ論的タコ - 数学の命題示しました

Combinatorial species (Combinatorial species - Wikipedia)は，離散オブジェクトの指数型母関数を扱うための現代的な手法である．
本稿ではspeciesの理論自体を説明することはしないが，大まかに言えばspeciesの理論は離散オブジェクトの組合せ論的な構造の情報を，直接母関数の等式へ変換する理論である．
詳しくは代表的な教科書Combinatorial Species and Tree-like Structuresをみるとよい．

本稿では，speciesの理論の練習問題としてよく登場するタコ (combinatorial octopus)と呼ばれるオブジェクトをspeciesの理論を用いて解析する．
本稿の元ネタは，上記教科書の練習問題である．

準備

まず，後に必要になるのでサイクルおよび長さ1以上の道の指数型母関数を求めておく．

サイクルとは， $n\ (n\geq 1)$ 個の要素を向きづけられた環状に並べる方法のことで，その数は円順列として馴染み深い $(n-1)!$ 通りである．
サイクルの指数型母関数は
$\displaystyle C(x)\triangleq\sum_{n\geq 1}\frac{x^n}{n!}(n-1)!=-\log(1-x)$
である．

長さ1以上の道とは， $n\ (n\geq 1)$ 個の要素を向きづけられた直線状に並べる方法のことで，その数は $n!$ 通りである．
長さ1以上の道の指数型母関数は
$\displaystyle L_{+}(x)\triangleq\sum_{n\geq 1}\frac{x^n}{n!}n!=\frac{1}{1-x}-1=\frac{x}{1-x}$
である．

タコの定義

タコとは，長さ1以上の道を，向きづけられた環状に $1$ 個以上並べる構造のことである．
例えば，下図は要素 $\{1,2,\ldots,17\}$ によるタコの一つである．

なお，今扱っているタコはラベル付きのタコである．グラフとして同型でもラベルが違うタコは区別する．

タコは，サイクルの一つ一つの点を，長さ1以上の道に置き換えた構造であると言える．
speciesの理論によれば，オブジェクトの世界での「点を別の構造に置き換える」操作は，母関数の世界での「代入」を意味するから，タコの母関数は
$\displaystyle {\rm Oct}(x)=\sum_{n\geq 0}\frac{x^n}{n!}{\rm Oct}_n=C(L_{+}(x))=-\log\left(\frac{1-2x}{1-x}\right)$
である．
ただし， $n$ 個の要素によるタコの数を ${\rm Oct}_n$ とかく．

ここから，要素数 $1,2,3,\ldots$ のタコの数はそれぞれ $1, 3, 14, 90, 744, 7560,\ldots$ である．
(OEIS: A029767)

サイクルとの間の全単射

タコの母関数は，次のように変形できる．
$\displaystyle {\rm Oct}(x)=-\log(1-2x)-(-\log(1-x))=C(2x)-C(x).$
ここから，オブジェクトの組合せ論的な対応関係
${\rm Oct}+C=C(2X)$
の成立が予想される．
上式はspeciesの言葉で書いてるが，speciesの言葉を使わないで書くと以下のことを言っている．

要素 $\{1,\ldots,n\}$ のタコの集合を ${\rm OCT}_n$ ，要素 $\{1,\ldots,n\}$ のサイクルの集合を ${\rm C}_n$ と書き，
要素 $\{1,\ldots,n\}$ の色付きサイクルの集合を ${\rm CC}_n$ と書く．
色付きサイクルとはサイクルの各点に対して色 $\in\{{\rm 赤},{\rm 青}\}$ を決めたものである．
これらの集合の間に全単射
${\rm CC}_n\to {\rm OCT}_n\sqcup {\rm C}_n$ がとれる．

（実際は，全単射がspeciesの同型となるためには，要素数が等しい以上の強い条件が必要である．）
これを満たす全単射は次のものがとれる．
色付きサイクルにおいて，赤い要素(Aとする)の次に青い要素(Bとする)が並んでいる場所があるとする．
このとき，Bから初めてサイクルを一周してAに至るまで，サイクル上の要素を順に見ていく．
今見ている要素が青いとき，キューにその要素をプッシュする．
今見ている要素が赤いとき，キューにその要素をプッシュし，そのキューをタコの触手の一本とする．この際，色はなくす．

これにより，タコができる．
要素がすべて赤い場合は，そのまま色をなくし触手の長さがすべて $1$ のタコとみなす．
要素がすべて青い場合は，タコは作らず，色をなくし要素数 $n$ のサイクルとみなす．

下図は， $n=8$ のときのこの対応の例である．

タコの数

タコの母関数
$\displaystyle {\rm Oct}(x)=C(2x)-C(x)$
を変形すると
$\displaystyle {\rm Oct}(x)=\sum_{n\leq 1}(n-1)!\frac{(2x)^n}{n!}-\sum_{n\leq 1}(n-1)!\frac{x^n}{n!}=\sum_{n\leq 1}(n-1)!(2^n-1)\frac{x^n}{n!}$
となるから，要素数 $n$ のタコの数は
${\rm Oct}_n=(n-1)!(2^n-1)$ である．