Stieltjes連分数のn階収束子はマッチング多項式の比である

概要

Stieltjes連分数を普通の分数で書いたときの式
$\displaystyle\cfrac{1}{1-\cfrac{a_1x}{1-\cfrac{a_2x}{\qquad\cfrac{\ddots}{1-a_kx}}}}=\frac{F(x)}{G(x)}$
において，多項式 $F,G$ がライングラフのマッチング多項式であることを示す．
証明はFlajoletの補題に基づいてStieltjes連分数をDyck路の母関数とみて，適当な対合を作る方法で行う．

用語の準備

Stieltjes連分数

列 $a_1,a_2,\ldots$ が与えられていて， $a_i\neq 0$ とする．自然数 $k$ に対して $k$ 階のStieltjes連分数 (S-連分数)とは，以下の連分数である．
$S_k(a;x)\triangleq\cfrac{1}{1-\cfrac{a_1x}{1-\cfrac{a_2x}{\qquad\cfrac{\ddots}{1-a_kx}}}}$

Dyck路

Dyck路と呼ばれる組合せ論的オブジェクトを定義する．
第一象限の整数点の集合 $\{(i,j)\mid i,j\geq 0, i,j\in\mathbb{Z}\}$ を節点集合とし，有向枝集合を
$(i,j)\to(i+1,j+1)\qquad i\geq 0,j\geq 0,\\ (i,j)\to(i+1,j-1)\qquad i\geq 0,j\geq 1$
で定めた有向グラフを考える．
このグラフにおいて，点 $(0,0)$ から点 $(0,2n)\ n\geq 0$ への道を，Dyck路という．
このグラフの枝重み $v$ を
$v( (i,j)\to(i+1,j+1))\triangleq 1\qquad i\geq 0,j\geq 0,\\ v( (i,j)\to(i+1,j-1))\triangleq a_jx\qquad i\geq 0,j\geq 1$
と定める．
この枝重みを使って，Dyck路 $\omega$ の重み $v(\omega)$ を，Dyck路に含まれる枝重みの積と定める．
但し $(0,0)$ から $(0,0)$ へ行く一点だけのDyck路の重みは $1$ とする．
Dyck路のピークとは，Dyck路において $(i,j)\to(i+1,j+1)\to(i+2,j)$ という順番で節点が出現する部分のことである．

また，雑に言い換えるとDyck路とは斜め上と斜め下のステップを組み合わせて， $(0,0)$ から出発して $y\geq 0$ の範囲からはみ出ないように $x$ 軸に戻ってくるような歩き方のことである．
$2n$ 歩のDyck路の数はカタラン数 $C_n$ であることが知られている．

上は，Dyck路の例である．その重みとピークを書いておいた．
上述の重み $v$ は，一点だけのDyck路の重みを $1$ とし，点 $(i,j)$ から斜め下に行くたびに $a_jx$ を掛けていくことを意味する．掛けるべき重みは，図中に赤字で書いてある．

S-連分数はDyck路の母関数である

組合せ論界隈ではよく知られているように，S-連分数はDyck路の母関数である．
第一象限において $0\leq y\leq k$ の範囲だけを動くDyck路の集合を $D_k$ と書くことにする．
例えば，上の画像のDyck路は， $D_3$ に含まれるが $D_2$ には含まれない．
このとき以下が成立する．
定理 (Flajoletの補題)
任意の自然数 $k$ に対して
$\displaystyle S_k(a,x)=\sum_{\omega\in D_k}v(\omega)$
が成り立つ．
この補題について詳しくは
Combinatorial aspects of continued fractions - ScienceDirect
を参照せよ．

マッチング多項式

整数 $s,t\ (s\leq t)$ が与えられているとする．集合 $\{i\mid s\leq i\leq t\}$ を節点集合とし，無向枝集合を $\{\{s,s+1\},\{s+1,s+2\},\ldots,\{t-1,t\}\}$ で定めた無向グラフを $[s,t]$ と書く．
グラフ $[s,t]$ のマッチングの集合を $M(s,t)$ と書く．
無向グラフのマッチングとは，枝集合の部分集合であって，pairwise disjointなもののことである．

グラフ $[s,t]$ の枝 $\{s,s+1\}$ の重みを $-a_{s+1}x$ と定め，マッチング $m\in M(s,t)$ の重みを $m$ に含まれる枝の重みの積と定め， $w(m)$ とかく．
但し，枝を一つも含まないマッチング $m=\emptyset$ の重みは $1$ とする．
マッチング $M(s,t)$ の母関数
$\displaystyle F_{s,t}(a;x)\triangleq \sum_{m\in M(s,t)}w(m)$
をマッチング多項式と呼ぶ．
普通はこの多項式を多少変形したものをマッチング多項式と呼ぶが，ここではめんどくさいのでこのように定義する．

上は $[0,3]$ のマッチングの集合 (左)と，それぞれのマッチングの重み (右)，そしてマッチング多項式 (下)を説明する図である．
なお，マッチング多項式 $F_{0,n}(a;x)$ は以下の漸化式で計算できる．
$F_0\triangleq 1,\ F_1\triangleq 1-a_1x,\ F_{n}\triangleq F_{n-1}-a_nxF_{n-2}$

$n$ 階のStieltjes連分数は，マッチング多項式の比である

定理
任意の自然数 $n$ に対して
$\displaystyle S_{n}(a;x)=\frac{F_{1,n}(a;x)}{F_{0,n}(a;x)}$
が成り立つ．
証明
等価な式
$F_{1,n}(a;x)=S_{n}(a;x)F_{0,n}(a;x)$
を示す．
集合 $I$ を $I\triangleq D_n\times M(0,n)$ とし， $I$ の部分集合 $J$ を
$J\triangleq\{(\omega,m)\mid \omega{\rm は一点のみのDyck路},\ m{\rm は点}0{\rm をマッチングに含まない}\}$
と定める．
すると，Flajoletの補題より右辺は集合 $I$ の母関数，左辺は集合 $J$ の母関数である．
つまり
$\displaystyle F_{1,n}(a;x)=\sum_{(\omega,m)\in J}v(\omega)w(m),\qquad S_n(a;x)F_{0,n}(a;x)=\sum_{(\omega,m)\in I}v(\omega)w(m)$
である．
よって，この等式を示すには，対合 $\varphi\colon I\setminus J\ni(\omega,m)\mapsto (\omega',m')\in I\setminus J$ であって，
$v(\omega)w(m)=-v(\omega')w(m')$
なるものを作ればよい．
組 $(\omega,m)\in I\setminus J$ が与えられたとき，非負整数 $p,q$ を以下で定める．
但しDyck路のピークの中で， $x$ 座標が一番小さいピークを最初のピークという．

Dyck路 $\omega$ に含まれる最初のピークが $(i,j)\to(i+1,j+1)\to(i+2,j)$ という形だとする．このとき $p\triangleq j+1$ とする．ピークが存在しないとき，つまり $\omega$ が一点だけのとき $p\triangleq -\infty$ とする．
マッチング $m$ に含まれる枝 $\{i,i+1\}$ のうち， $i$ が最小のものをとり $q\triangleq i+1$ とする．枝が存在しないとき，つまり $m=\emptyset$ のときは $q\triangleq \infty$ とする．

そして対合で移る相手 $(\omega',m')$ を以下の通り定める．

$p+1\geq q$ のとき，マッチングの枝 $\{q-1,q\}$ を取り除き，Dyck路 $\omega$ において $(q-1,q-1)\to(q,q)\to(q+1,q)$ という部分を挿入する．(これは必ず可能である．)
$p+1\lt q$ のとき，Dyck路の最初のピークすなわち $(p-1,p-1)\to(p,p)\to(p+2,p-1)$ という部分を取り除き，マッチングに枝 $\{p-1,p\}$ を加える．(これも必ず可能である．)

このように $\varphi$ を定めればそれは重みの符号を反転する対合である．
（証明終わり）

上は対合の様子を説明する図である．Dyck路とマッチングの組 $(\omega,m)$ をとったとし，
図中の $y$ 軸にあたる部分に，マッチング $m$ を縦向きに置いてある．(a)ではマッチングの赤い部分につけられた重みが $-a_qx$ であるが，対合で移したあとの (b)ではDyck路に挿入された赤い部分の重みが $a_qx$ に変わっており，重みの符号が反転していることがわかる．