閉路グラフのマッチングを有限オートマトンで記述する

Viennot先生の講義動画で，組合せ論的オブジェクトを有限オートマトンへ全単射的に変換して，母関数を簡単に求める方法が紹介されていました．
動画では，道グラフのマッチング（その個数はフィボナッチ数）を状態数2の有限オートマトンに変換していました．

youtu.be

この記事では，同じようにして閉路グラフのマッチングを有限オートマトンに変換して母関数を求めてみます．
グラフのマッチング，および閉路グラフやそのマッチング多項式については，以前の記事を参照してください．
iwalion.hatenablog.com

有限オートマトン

この記事では，有限オートマトンとは有向グラフ上の自己交差を許す歩道のことだと思ってかまいません．
この記事ではViennot先生の動画で紹介されている次の定理を使います．証明は動画を見てください．
定理
節点数 $n$ の有向グラフ $G$ と枝重み $w:E(G)\to \mathbb{K}$ が与えられているとする．
有向グラフ上の歩道 $\omega$ の重み $w$ を，それが通る枝の重みの積により定める．有向グラフの隣接行列を $A=(a)_{i,j}$ とする．
逆行列 $(I-A)^{-1}$ が存在すると仮定する．
このとき，節点 $i$ から節点 $j$ へ行く全ての歩道の重みの和 (一般には無限和)は， $(I-A)^{-1}$ の $(i,j)$ 要素で与えられる．

道グラフのマッチング

長さ $n$ の道グラフとは，節点集合 $V\triangleq\{1,\ldots,n\}$ と枝集合 $E\triangleq\{\{1,2\},\{2,3\},\ldots,\{n-1,n\}\}$ からなる単純無向グラフです．
長さ $n$ の道グラフのマッチングの個数は，フィボナッチ数 $F_{n+1}$ です．下図に長さ $4$ の道グラフと，そのマッチングの集合を描きました．

長さ $n$ の道グラフのマッチングの集合は，下図 (図１)に示す状態数2の有限オートマトン $G_1$ によって受理される長さ $n$ の言語の集合と一対一対応します．

図１はただの有向グラフだと思ってもかまいません．その場合，図中の $a,b,c$ は枝重みだと思ってください．グラフ理論の言葉で言うなら，節点 $s_1$ から節点 $s_1$ への長さ $n$ の歩道の集合と全単射であるということです．

どんな全単射かは，下の図を見れば分かる気がします．道グラフの節点 $1$ から節点を順に見ていきマッチングに含まれない節点ならば $s_1$ の自己ループを通り，マッチングに含まれる節点ならば $s_1\to s_2\to s_1$ を通ります．

フィボナッチ数の母関数

このことを使って，道グラフのマッチングの個数の母関数や，マッチング多項式の母関数を求めることができます．
ここでは，個数の母関数を求めてみます．
個数の母関数とは，無限和 $\displaystyle\sum_{n\geq 0} M_nt^n$ のことです．但し長さ $n$ の道グラフのマッチングの個数を $M_n$ と書きました．
図１の有向グラフにおける枝重み $a,b,c$ をそれぞれ $a=b=c=t$ と定めます．
すると，先に述べた全単射から
$\displaystyle\sum_{n\geq 0} M_nt^n=\sum_{\omega\colon (s_1\to s_1)}w(\omega)$
です．和の範囲 $\omega\colon (s_1\to s_1)$ は，グラフ $G_1$ において $s_1$ から $s_1$ に行く全ての歩道について和を取るという意味です．

これは，最初に書いた定理から，グラフ $G_1$ の隣接行列を使って計算できます．グラフ $G_1$ の隣接行列は

なので， $(I-A)^{-1}$ の $(1,1)$ 要素を計算すれば，
$\displaystyle\sum_{n\geq 0} M_nt^n=\frac{1}{1-t-t^2}$
が分かります．

閉路グラフのマッチング

次に，同じことを閉路グラフのマッチングでやってみます．閉路グラフとそのマッチングとは，以下のようなものでした．これは $n=5$ の例です．

閉路グラフの節点を $\{1,2,\ldots,n\}$ とするとき，マッチングに枝 $\{n,1\}$ が含まれているかどうかで，オートマトンの別々の部分に飛ばすようにします．
以下のようなオートマトンが得られました．

定理
$n\geq 3$ のとき，大きさ $n$ の閉路グラフのマッチングの集合は，以下の有向グラフ $G_2$ において，節点 $s$ から節点 $g_1$ または $g_2$ への長さ $n$ の歩道の集合と一対一対応する．

書くのがダルくなってきたので，なんでそうなるのかは考えてください．節点 $g_1$ にたどり着くのが枝 $\{n,1\}$ が含まれている場合で，節点 $g_2$ が含まれていない場合です．

閉路グラフのマッチング多項式の母関数

有向グラフ $G_2$ の枝重みを次のように定めます．

すると， $G_2$ における「節点 $s$ から，節点 $g_1$ または $g_2$ への長さ $n$ の歩道の重みの和」は，閉路グラフのマッチング多項式 $C_{\gamma_n}(x)$ になります．
さらに， $G_2$ の隣接行列 $A_2$ を考え，行列 $(I-A_2)^{-1}$ の $(s,g_1)$ 成分と $(s,g_2)$ 成分の和をとることで，
閉路グラフのマッチング多項式の母関数が
$\displaystyle \frac{1-t^2}{1-tx+t^2}$
であることが分かります．