数理解析研究所講究録 1422 巻 2005 年 154-174

154

可積分系のグラフ論的描像について

Graph Theoretical Aspects of Integrable Systems
京都大学情報学研究科 中村 佳正 1 (Yoshimasa Nakamura)

Depart. of Appl. Math. and Phys., Grad. School of Informatics, Kyoto Univ.
京都大学情報学研究科 上岡 修平 2 (Shuhei Kamioka）
Depart. of Appl. Math. and Phys., Grad. School of Informatics, Kyoto Univ.
京都大学情報学研究科 大平 倫宏 3 (Norihiro Ohira)Depart. of Appl. Math. and Phys., Grad. School of Informatics, Kyoto Univ.

Abstract. Graph theoretical aspects of certain integrable systems are discussed including thesemi-infinite and the infinite Toda chains, the recurrence relations of the qd and the FG algorithms. Hankel determinants of various combinatorial numbers are computed as tau-function
solutions of the Toda chains. Weighted sums of the Dyck paths and the Sch\"oder paths are also
computed through Hankel and Toeplitz determinants of certain combinatorial numbers, respectively.

1

はじめに

組合せ論的数のなす Hankel 行列式は関連するグラフの重みを表す重要な量として捉えられ, 従来は様々な離散数学的手法で計算されてきた (cf. [1, 4]). 一方, 可積分系の Lax 対によって直交多項式の 1 パラメータ変形が誘導されることに基づいて, 可積分系のタウ関数解のモーメントによる

Hankel 行列式表示が得られている. このことから, 組合せ論的数のなす Hankel 行列式を通じて, 可積分系のグラフ論的描像を論じることが可能になる.
本報告の前半部分では, 連続時間の戸田方程式に基づく, 種々の組合せ論的数の Hankel 行列式の計算について説明する. 第 2 節では, 半無限戸田方程式の変数分離解について, Sheffer クラスの直交多項式との密接な関係を述べつつ, Euler 数, Bell 数等の指数型の母関数を持つ組合せ論的数について報告する [9], 第 3 節では, 無限戸田方程式の特殊解である 0 ソリトン解 (真空解) について考察し, 直交多項式の Geronimus, Christoffel 変換に着目して, Catalan 数を含むクラスの組合せ論
的数のなす Hankel 行列式を具体的に書き下す [10].
後半では, 離散可積分系とグラフ論で取り扱われる組合せ論的数の関係を明らかにし, 種々の組
合わせ論的量を離散可積分系を用いた計算方法を定式化する. 第 4 節においては, Dyck path に関連した
アルゴリズムのグラフ論的な解釈を与えた Viennot(2000) の研究 [12] を解説する. Hankel
行列式はグラフの重みの総和というグラフ論的意味をもつ. 重みが 1 の場合はグラフの本数の数
え上げに相当する. 第 5 節では, Schr\"oder path とアルゴリズムとアルゴリズムとの間に,Dyck path と同様な密接な関係があることを新たに示し, Toeplitz 行列式のグラフ論的意味を考察して, Schr\"oder path の重みの総和の計算等,
アルゴリズムの組合せ論への応用について論じる.
$\mathrm{q}\mathrm{d}$$\mathrm{F}\mathrm{G}$$\mathrm{F}\mathrm{G}$

1 ynaka@am$\mathrm{p}\mathrm{i}$kyoto$\mathrm{u}$$\mathrm{a}\mathrm{c}$jp2kamioka@amp.i.kyoto-uac jp$3_{\circ \mathrm{h}_{\overline{1}}\mathrm{r}\mathrm{a}@\mathrm{a}\mathrm{m}\mathrm{p}.\mathrm{i}}$kyoto-u ac.jp$\mathrm{q}\mathrm{d}$155

半無限戸田方程式と Sheffer クラスの組合せ論的数

2

半無限戸田方程式の変数分離解は, Sheffer クラスの直交多項式によって分類可能となる [9]. さらに, それぞれの直交多項式に組合せ論的数が対応し, それらのなす Hankel 行列式が半無限戸田方

程式のタウ関数解として計算可能である.

21

半無限戸田方程式の変数分離解

3 項漸壁式$P_{n+1}(x)+b_{n}P_{n}(x)+u_{n}P_{n-l}(x)=xP_{n}(x)$$P_{0}=1$で定義されるモニックな$n$,$P_{1}(x)=x-b_{0}$,(1)$(u_{n}\neq 0, n=1,2, \ldots)$

次多項式 $P_{n}(x)$ に対して

(2)$\sigma(P_{n}(x)P_{m}(x))=h_{n}\delta_{nm}$なる直交関係を満たす線形汎関数 が存在する.
のなす Hankel 行列式$\sigma$$\sigma$$D_{n}=\det(c_{i+j})|_{\dot{x},j=0}^{n-1}$

は $D_{n}>0$ を満たし,,が定めるモーメント $c_{n}=\sigma(x^{n}),$ $(n=0,1, \ldots)$$D_{0}=1$,(3)$D_{-1}=0$

これを用いて直交多項式 $P_{n}(x)$ の表現$c_{0}$$c_{1}$$c_{n}$$c_{1}$$c_{2}$Cn 十 l(4)$P_{n}(x)= \frac{1}{D_{n}}$が得られる. ここでパラメータ$t$

C ユー 1$c_{n}$

1$x$$c_{2n-1}$$x^{n}$

によるモーメントの変形$\frac{dc_{n}}{dt}=c_{n+1}$を導入する. このとき, 直交多項式の係数$u_{n}= \frac{D_{n-1}D_{n+1}}{D_{n}^{2}}$

,

,

(5)

$(n=0,1, \ldots, t\in \mathrm{R})$$\{u_{n}, b_{n}\}$は Hankel 行列式 (3) を用いて

(6)$b_{n}= \frac{1}{D_{n+1}}\frac{dD_{n+1}}{dt}-\frac{1}{D_{n}}\frac{dD_{n}}{dt}$と書け, 半無限戸田方程式$\frac{du_{n}}{dt}=u_{n}(b_{n}-b_{n-1})$,$\frac{db_{n}}{dt}=u_{n+1}-u_{n}$,$u_{0}=0$,$(n=0,1, \ldots)$(7)を満足する, 半無限戸田方程式を双線形形式で書くと$(\mathrm{S}\rangle$$D_{n+1}D_{n-1}=D_{n} \frac{d^{2}D_{n}}{dt^{2}}-(\frac{dD_{n}}{dt})^{2}$となり, これは (5) を通じて Sylvester の行列式恒等式に帰着する.

半無限戸田方程式の特殊解として, モーメントが$c_{n}(t)=T_{n}(y(t))c_{0}(t)$,(9)$(n=0,1, \ldots)$と表されている場合を考察する. ただし, $T_{n}(y(t))$ はある未知関数 $y(t)$ の次の定理が成り立つ.
$T_{n}(y(t))$ は直交多項式とは限らない. このとき,$n$次の多項式とする.

156

定理 1. ([9]) モーメント $c_{n}(t)=T_{n}(y(t))c_{0}(t)$ が半無限戸田方程式の解を与えることと以下の$\mathrm{A})\sim \mathrm{C})$が成り立つことは同値である.

A) 関数 $y(t)$ は方程式$\frac{dy(t)}{dt}=\sigma(y)$の解である, ただし,

B)$t\langle y$$\sigma(y)$は $\sigma(y)=\xi y^{2}+\eta y+\zeta$ なる) を $y(t)$ の逆関数とみての関数$y$の 2 次以下の(非零) 多項式は方程式$\phi(y)\equiv c_{0}(t\langle y))$$\phi’(y)=\frac{\tau(y)}{\sigma(y)}\phi(y)$の解である. ただし,C)$\alpha\neq 0$と$\beta$$\tau(y)$は任意定数で,は $\tau(y)=\alpha y+\beta$ なる $y$ の 1 次式$\alpha$

と

$\xi$

の間には

$\xi\neq-\frac{\alpha}{n}$,$(n=1,2, \ldots)$の関係式が成り立つ.
この結果, $T_{n}(y(t))$ は$\sigma(y),$を用いて逐次的に定まり, このクラスの変数分離解は完全に分$\tau(y)$類される.
系 1. モーメント$\mathrm{c}_{n}$(が果 (t) $=T_{n}(y(t))c_{0}(t)$ を満たすとき, 次の )$t\rangle$$\mathrm{I}$$\sim \mathrm{I}\mathrm{I})$が成り立つ,

1) 直交多項式の漸化式の係数は,$b_{n}(t(y))$$=$$\tau(y)+n\sigma’(y)$$u_{n}(t(y))$$=$$n \sigma(y)(\tau’(y)+\frac{1}{2}(n-1)\sigma’’(y))$$=$$n(\alpha+(n-1)\xi)\sigma(y(t))$(10)と書かれ, $u_{n}=u_{n}(t)$ は半無限戸田方程式(11)$\frac{d^{2}\log u_{n}}{dt^{2}}=u_{n+1}-2u_{n}+u_{n-1}$の変数分離解を与える.

Il) 対応する 3 項漸化式 (1) は Sheffer クラス (Meixner, Laguerre, Pollaczek, Chalier, Hermite)の直交多項式 (cf. [3]),$P_{n+1}(x)+(\beta\gamma+n(v_{3}+v_{4}))P_{n}(x)+n(n+\gamma-1)v_{1}v_{2}P_{n-1}(x)=xP_{n}(x)$

を与える.

,

$P_{1}(x)=x-\beta\gamma$,$\sum_{n=0}^{\infty}P_{n}.(x)\frac{t^{n}}{n!}=A(t)e^{xF(t)}$,$P_{0}=1$(12)$(A(0)=1, F(0)=0)$

(13)

157

22

Sheffer クラスの組合せ論的数のなす Hankel 行列式

定理 1. における $\sigma(y)=\xi y^{2}+\eta y+\zeta$ の選択を通じて変数分離解を分類すれば, 対応するモーが種々の組合せ論的数の母関数となることがわかる. さらに, 半無限戸田方程式のタメント$c_{0}(t)$ウ関数解 $D_{n}(t)$ を通じて, これらの組合せ論的数の Hankel 行列式 $D_{n}(0)$ を帰納的に書き下すことができる. 表 1 のように対応する組合せ論的数, She 伍 er クラス, Hankel 行列式等は 5 つの場合に分類される.
$\text{表}1$3: semi-infinite Toda chain, combinatorial numbers
and orthogonal polynomails of Sheffer class

無限戸田方程式と Catalan クラスの組合せ論的数
半無限戸田方程式と同様に無限戸田方程式にも組合せ論との対応関係が存在し, 特に 0 ソリト

数を含む組合せ論的数のクラスと対応している. 本節では直交多項式理論におけるモーメントと直交多項式の Geronimus, Christoffel 変換に着目し, これらの変換によっ
ン解 (真空解)は Catalanて生成される組合せ論的数のなす Hankel 行列式を導出する [10].

158

3.1

無限戸田方程式と Geronimus 変換による Catalan クラスの組合せ論的数のなす Hankel 行列式の計算

まず, Catalan 数$C_{n}$の定義, 具体例, 漸化式を与える (図 1 参照).

原点 $(0, 0)$ と点 $(2n, 0)$ を結ぶ格子路のうち, 条件 $y\geq 0$ を満たすものの本数(長さ $2n$ の Dyck path の本数に一致する)$C_{0}=1,$ $C_{1}=1,$ $C_{2}=2,$ $C_{3}=5,$ $C_{4}=14,$ $C_{5}=42,$$c_{n}= \sum C_{k}C_{n-k-1}n-1$$\ldots$.

$k=0$$\Lambda_{--}^{l}’\ulcorner^{---}-\lrcorner\{$$\overline{\overline{\overline{\overline{\overline{\overline{\acute{m}}}}}}}^{1}\ulcorner-|--|\mathcal{T}^{-}--1\overline{\mathfrak{l}}\overline{|}\downarrow-\wedge-\mathrm{J}----\urcorner\urcorner^{\urcorner}|^{1}||$$C_{1}=1$$C_{2}=2$,$1’|..||t^{--+_{\mathrm{I}}}|\llcorner|\{\mathrm{I}-\dashv_{\mathrm{I}1\grave{\mathrm{t}}}---\dashv \mathfrak{l}--\mathrm{I}_{\mathfrak{l}\mathrm{i}}\ulcorner--|--\tau-\mathrm{I}\overline{\mathrm{I}}_{1}-\lrcorner-\mathrm{I}-|----1-1_{--}\mathrm{a}-- \mathfrak{l}\mathrm{I}-\neg|--|-- \mathrm{r}^{1}-.-\rceil-----$$C_{3}=5$

図 1: Catalan number.

同様に, Motzkin 数$M_{n}$の定義, 具体例, 漸化式は以下の通りである (図 2 参照).

原点 $(0, 0)$ と点 $(n, 0)$ を結ぶ格子路のうち, 条件 $y\geq 0$ を満たすものの本数(ただし, 長さ 1 の横方向へのステップを許す)$M_{0}=1,$ $M_{1}=1,$ $M_{2}=2,$ $M_{3}=4,$ $M_{4}=9,$ $M_{5}=21,$$M_{n}=M_{n-1}+ \sum_{k=0}^{n-2}M_{k}M_{n-k-2}$$\ldots$.

$\underline{|\ulcorner^{--}||}$$\mathrm{r}^{\mathfrak{l}\mathrm{I}}|\ulcorner^{--}\ulcorner_{1}^{--}$$M_{1}=1$「$||_{1}R_{--}^{--}\ulcorner^{-}1-\rfloor$$M_{2}=2$「$-\mathrm{T}^{--\ulcorner^{--}}||-$」,$-\mathrm{J}_{--}\mathrm{J}_{--}\mathrm{T}^{\ulcorner_{1}}$$\overline{\overline{\overline{\overline{\overline{\mathrm{r}}}}}}_{\mathrm{I}1_{\mathfrak{l}}^{\mathrm{I}}}^{11}||\ulcorner^{--\lrcorner}|$$\mapsto^{1}|\ulcorner^{-++_{1}^{j}}\mathrm{J}’$$\overline{\overline{\overline{\overline{\overline{m}}}}}_{--}^{\mathrm{I}}1\ulcorner^{--+_{l}^{1}}|_{\downarrow}--\mathrm{J}1\mathrm{I}\mathrm{I}\acute{\mathfrak{l}}-\ulcorner_{1,-\lrcorner}$$‘\infty_{--\mathrm{J}_{--}}\ulcorner^{-+_{1\mathrm{I}\mathrm{I}}^{--A}}|1\Gamma^{--}\ulcorner^{-}1\mathrm{T}_{\mathrm{t}}^{1}--$$NI_{3}=4$

図 2: Motzkin number.

さて, 初期条件$\tau_{1}=\varphi(t)$,$\tau_{0}=1$,$\tau_{-1}=\psi(t)$

(14)

159

(ただし,

$\varphi,$は$\psi$$t$の任意関数) に対する無限戸田方程式$\frac{d^{2}\tau_{n}}{dt^{2}}\tau_{n}-(\frac{d\tau_{n}}{dt})^{2}=\tau_{n-1}\tau_{n+1}-\varphi\psi\tau_{n}^{2}$

,

(15)

$(n\in \mathrm{Z})$のタウ関数解は$\tau_{n}=|\begin{array}{lll}a_{0} a_{n-1}\vdots \ddots \vdots a_{n-1} a_{2n-2}\end{array}|,$$(n>0)$ ,$a_{n}= \frac{da_{n-1}}{dt}+\psi\sum_{k=0}^{n-2}a_{k}a_{n-k-2}$$b_{n}= \frac{db_{n-1}}{dt}+\varphi\sum_{k=0}^{n-2}b_{k}b_{n-k-2}$$(n<0)$(16)$(a_{0}=\tau_{1}=\varphi)$(17)$(b_{0}=\tau_{-1}=\psi)$

(18)

,

,

$\tau_{n}=|\begin{array}{lll}b_{0} b_{-n-1}\vdots \ddots \vdots b_{-n-1} b_{-2n-2}\end{array}|,$で与えられる [7].

以下では, 特殊解として$\psi=\beta e^{-\gamma t}$

なる,$\varphi=\alpha_{0}e^{\gamma t}$($\alpha 0,$$\beta,$$\gamma$(19): 任意定数)でi 解) を考える. このとき,によって特徴づけられる 0 ソリトン解 (なる
通常母関数, $n>0$
は定数となり, 無限戸田方程式 (15) を帰納的に用いると,$\alpha_{n}:=a_{n}e^{-\gamma t}$$\ovalbox{\tt\small REJECT}_{\neg}^{\overline{*}}Z$$\varphi,$

定まる$\psi$$\alpha_{n}\text{の}$$\alpha_{n}$タウ関数$\tau_{n}$は, それぞれ,$F(x):= \sum_{n=0}^{\infty}\alpha_{n}x^{n}$(20)$\tau_{n}(t)=\alpha_{0^{n}}(\alpha_{0}\beta)e^{\gamma nt}\uparrow \mathrm{t}(\mathrm{v}\iota_{\vec{2}}-1$と表される. 任意定数$\alpha_{0},$$\beta,$$\gamma$の選択によりi) $\alpha 0=1,$ $\beta=1,$ $\gamma=0$ ととったとき,応する.
$\mathrm{i}\mathrm{i})\alpha_{0}=1,$$\beta=1,$ $\gamma=1$

これらの場合,同としたとき,$\alpha_{n}$$\alpha_{n}$$\alpha_{n}$は種々の組合せ論的数となる.

は $\alpha_{2n}=C_{n},$ $\alpha_{2n+1}=0$ により Catalan 数

は $\alpha_{n}=M_{n}$ により Motzkin 数 $M_{n}$ と–$C_{n}$と対する,なす Hankei 行列式は布 (0) $=3,$ $(n=1,2, \ldots)$ となる (cf. [1, ).
\not\in ‘定数) により導( $n=1,2,$をについて g に定数$4_{\rfloor}^{\rceil}$$\alpha_{n}\text{の}$$_{\llcorner}^{-}$$\alpha_{n}’$$\llcorner^{\backslash }\backslash \text{特_{}\backslash }\Re \text{解}$$\alpha_{n+1}’:=a_{n}e_{\dot{\mathit{1}}}^{-\gamma t}$$\alpha_{1}’:$$\ldots,$

入する. 変換(21)$\alpha_{n}arrow\alpha_{n}’=\alpha_{n-1}$は直交多項式論におけるモーメントの Geronimus 変換である. このとき,$\alpha_{n}’$の通常母関数は(22)$F(x):= \sum_{n=0}^{\infty}\alpha_{n}’x^{n}=$となる. また, Hankel 行列式$H_{n}:=\det(\alpha_{i+j}’)|_{\dot{\mathrm{z}},j=0}^{n-1}$に対して Pl\"ucker 関係式,$\xi_{0}^{0}.\cdot.\cdot \mathrm{j}\div\ovalbox{\tt\small REJECT}_{1}^{1}\xi_{1n+1}^{0..\cdot.n}..-\xi_{1n}^{0.\cdot n-1}.].\xi_{0\cdot n}^{0\cdot..\cdot n-1,n-\vdash 1}.+\xi_{1-\cdot\cdot n-1,n+1}^{0\cdots n-1}.\xi_{0\cdots n}^{0\cdots n}=0$

(23)

160

と Sylvester 恒等式(24)$D(\begin{array}{ll}1 n+1n +1n\end{array})D=D(\begin{array}{l}1n\end{array})D(\begin{array}{l}n+1+1n\end{array})-D(\begin{array}{ll} 1n +1\end{array})D(\begin{array}{ll}n +1 n\end{array})$を用いることにより,$H_{n}$の満たす 3 項漸化式

$H_{n+1}=(\alpha_{1}’)^{n}\beta^{n-1}\gamma H_{n}-(\alpha_{1}’)^{2n}\beta^{2n-2}H_{n-1}$,$H_{0}=1$ ,(25)$H_{1}=\alpha_{0}’$が得られる.
任意定数
式$H_{n}$$(\alpha_{0}’, \alpha_{1}’, \beta, \gamma)$を具体的に与えると, ),$\mathrm{i}$$\mathrm{i}\mathrm{i}\rangle$

以外の組合せ論的数$\alpha_{n}’$のなす Hankel 行列が書き下される [10]. 例えば,のとき,$\mathrm{i}\mathrm{i}\mathrm{i})(\alpha_{0}’, \alpha_{1}’, \beta, \gamma)=(a, b, 1,2a)$$K_{n}(a, b)$$\alpha_{n}’$は一般化 Catalan 数 $K_{n}(a, b)$ に一致する,$\alpha_{n}’=$. 3 項欧化式は $H_{n+1}=2ab^{n}H_{n}-b^{2n}H_{n-1}$ となり, 特に, $H_{n}(a=x, b=1)$ はChebyshev 多項式である.
$\mathrm{i}\mathrm{v})(\alpha_{0)}’\alpha_{1)}^{f}\beta, \gamma)=(1,1, m+1, m+2)$$\alpha_{n}’(m)=S_{n}(m)$.

$\alpha_{n}’$のとき,のなす Hankel 行列式$\alpha_{n}’$$H_{\mathrm{n}}$は $m$ -color super Catalan 数 $S_{n}(m)$となる,は $H_{n}(m)=(m+1)^{n(n-1)/2}$ である.

は Narayama 多項式 $N_{n}(w)$ に一致する,
v) $(\alpha_{0}’, \alpha_{1}’, \beta, \gamma)=(1, w, 1, w+1)$ のとき,
. Narayama 多項式のなす Hankel 行列式は $H_{n}(w)=(w+1)^{n(n-1)/2}$ となる.
$\alpha_{n}’$$\alpha_{n}’=$$N_{n}(?L^{1})$$\mathrm{v}\mathrm{i})(\alpha_{0}’, \alpha_{1}’, \beta, \gamma)=(1,1,1, \gamma)$のとき,$\alpha_{n}’$は polyomino 数と呼ばれる数となる, $\alpha_{n}’(\gamma=3)=P_{n}$ .

3 項漸化式は $H_{n+1}=\gamma H_{n}-H_{n-1}$ となるが, $\gamma=3$ のとき Hankel 行列式は奇数番の Fibonacci
数に一致する. $H_{n}(\gamma=3)=F_{2n-1}$ .
は Catalan 数を用いて $\alpha_{n}’(m)=m^{n}C_{n}$ と書かれる.
のとき,この数のなす Hankel 行列式は $H_{n}(m)=m^{n(n-1)}$ である.

$\mathrm{v}\mathrm{i}\mathrm{i})(\alpha_{0}’, \alpha_{1}’, \beta, \gamma)=(1,1, m, 2m)$

ここで,$\mathrm{i}\mathrm{v}$$\alpha_{n}’$) に現れた $m$ -color super Catalan 数 $S_{n}(m)$ の定義, 具体例を与える (図 3 参照),

原点 $(0, 0)$ と点 $(2n, 0)$ を結ぶ格子路のうち, 条件 $y\geq 0$ を満たすものの本数(ただし, $m$ 種類の長さ 2 の横ステップを含む)

So (1) $=1,$ $S_{1}(1)=1,$ $S_{2}(1)=3,$ $S_{3}(1)=11,$ $S_{4}(1)=45,$$\Lambda_{--}^{\mathrm{I}}|\ulcorner^{---}--\mathrm{J}\mathrm{I}\mathrm{I}$$S_{1}(1)=1$$S_{2}(1)=3$

図 3: super Catalan number.

$\ldots$

161

また,

$\mathrm{v}\mathrm{i}$) の polyomino 数$P_{n}$の定義具体例は次のように与えられる (図 4 参照).

斜線付きの正六角形を元に,$n$個の正六角形を隣接させる場合の数(ただし, 六角形の隣り合う 2 辺が同ときに他の六角形に接してはならない)$P_{0}=1,$ $P_{1}=1,$ $P_{2}=3,$ $P_{3}=10,$ $P_{4}=36,$$P_{1}=1$$P_{2}=3$$\ldots$$\ovalbox{\tt\small REJECT}\subseteq\}$

さ$\ovalbox{\tt\small REJECT} 8$$\subset_{\mathrm{b},\ovalbox{\tt\small REJECT}}$$\ovalbox{\tt\small REJECT}=10$

図 4: polyom$\mathrm{i}\mathrm{n}\mathrm{o}$number.

31 節の結果は以下の表 2 のようにまとめられる. 2 節で扱った Sheffer クラスの直交多項式で行
はな , Chebyshev 多項式のクラスが現れている. 表 2 では, 既存の組合せ論的数のなす Hankel
列式を与えているが, これ以外にも名前のわからない組合せ論的数のなす Hankel 行列式も多数導$\langle$

出されている.

12: infinite Toda chain and combinatorial numbers

1B2

32

無限戸田方程式と Christoffel 変換による Catalan クラスの組合せ論的数のなす Hankel f/r 列式の計算

前節では主に直交多項式論における Geronimus 変換に対応する Hankel 行列式について紹介した. 直交多項式論では Geronimus 変換の逆変換として,(26)$\alpha_{n}arrow\alpha_{n}’=\alpha_{n+1}-x\alpha_{n}$なる Christoffel 変換が存在する. 本節では Christoffel 変換で定義される組合せ論的数$\alpha_{n}’$のなす

Hankel 行列式を考察する,$\alpha_{n}$をモーメント列としてもつ線形汎関数とそれに付随する$\sigma$$Q_{n+1}(x)=(a_{n}x+b_{n})Q_{n}(x)-c_{n}Q_{n-1}(x)$$\sigma(Q_{n}(x)Q_{m}(x))=\delta_{nm}$,$\alpha_{n}=\sigma(x^{n})$

,

,

$n$

次直交多項式 $Q_{n}(x)$$Q\mathrm{o}=1$,$(n=1,2, \ldots)$(27)$(n=0,1, \ldots)$を考える. 直交多項式 $Q_{n}(x)$ は行列式を用いて

Q 賦 x)$=$$\frac{1}{\sqrt{H_{n-}{}_{1}H_{n}}}|\begin{array}{lll}\alpha_{0} \alpha_{1} \alpha_{n}\alpha_{1} \alpha_{2} \alpha_{n+\mathrm{l}}\cdots \cdots \cdots\alpha_{n-1} \alpha_{n} \alpha_{2n-\mathrm{l}}1 x x^{n}\end{array}|$$=$$\frac{(-1)^{n}}{\sqrt{H_{n-}{}_{1}H_{n}}}|\begin{array}{llll} \alpha_{\mathrm{l}}-x\alpha_{0} \alpha_{2}-x\alpha_{1} \alpha_{n}-x\alpha_{n-1} \alpha_{2}-x\alpha_{1} \alpha_{3}-x\alpha_{2} \alpha_{n+1}-x\alpha_{n}| \alpha_{n}-x\alpha_{n-1} \alpha_{n+1}-x\alpha_{n} \alpha_{2n-\mathrm{l}}-x\alpha_{2n-2}\end{array}|$$(2\mathrm{S})$と表わすことができる. $\alpha_{n}’=\alpha_{n+1}-x\alpha_{n}$ とおけば, (28) は直交多項式 $Q_{n}(x)$ は Christoffel 変換されたモーメントとから$\alpha_{n}’$$\alpha_{n}’$のなす Hankel 行列式と (定数倍を除いて) 等しいことを示している.

このこのなす Hankel 行列式が$\ovalbox{\tt\small REJECT}(x)$$\alpha_{0}’$$\alpha_{1}’$$\alpha_{\mathrm{n}-1}’$$\alpha_{1}’$$\alpha_{2}’$$\alpha_{n}’$$(x)=(-1)^{n}\sqrt{H_{n-}{}_{\mathrm{J}}H_{n}}Q_{n}(x)$$:=$$\alpha_{n-1}’$(29)$\alpha_{2n-1}’$$\alpha_{n}’$と計算される.

例として, $x=-1$ とおき, Catalan 数の隣接和 $\alpha_{n}’=\alpha_{n+1}+\alpha_{n}=C_{n+1}+c_{n}$ を考える. 直交多項式の係数は行列式 $H_{n}=1$ から計算され $a_{n}=1,$ $b_{n}=-2(n\geq 1),$ $b_{0}=-1,$ $c_{n}=1$ となり, 3
項賦活式は $Q_{n+1}(x)=-(x-2)Q_{n}(x)-Q_{n-1}(x)$ と書き下される. $x=-1$ とすれば Catalan 数の隣接和のなす Hankel 行列式は Fibonacci 数を用いて$H_{n}’$,$:=\det(C_{i+j+1}+C_{i\dagger j})|_{i,j=0}^{n-1}=F_{2n+1}$と表される.

$H_{n}’$$:=\det(C_{i+j+2}+C_{\dot{q}+j+1})|_{i,j=0}^{n-1}=F_{2n+2}$

163

4

$\mathrm{q}\mathrm{d}$アルゴリズ$\Delta$と重み付き Dyck path

アルゴリズムのグラフ論的解釈が Viennot[12] によって与えられている. その過程において,アルゴリズムを用いた path
連分数や Hankel 行列式のグラフ論的な解釈が可能となり, この結果,$\mathrm{q}\mathrm{d}$$\mathrm{q}\mathrm{d}$アルゴリズムは離散時間半無限戸田方程式に他の重みの総和等の計算方法が定式化されている.
アルゴリズムの重み付き Dyck path への応用を解説する.
ならない, 本節では, [12] に基づいて$\mathrm{q}\mathrm{d}$$\mathrm{q}\mathrm{d}$4.1

重み付き Dyck pathNE(右斜め上) ステップ, SE(右斜め下) ステップのみによって構成される $(0, 0)$ から $(2n, 0)$ ま
での長さ $2n$ の格子路を Dyck path という. NE, SE ステップについては図 5,6 参照.
$.\mathrm{h}_{j_{-\sim\sim--}}^{\mathrm{I}}|j..\cdot.\mathrm{i}\mathrm{i}$$\overline{\mathrm{i}}...f_{-\cdot-}^{\dot{}}.\underline{}$

図 6: SE step.

図 5: NE step.

から始まる NE ステップには重み 1 が SE ステップには重み $\beta_{h}(1\leq h<\infty)$ が付い
つているとする (重み付き Dyck path). Dyck path の性質より 1 つの NE ステップの後には必ず 1
今, 高さ

$h$

よって, このように SE ステップだけに重みを付けても一般
以下, 1 本の格子路を $w$ で表し, その path の長さを length(w) とかく. これは NE,の SE ステップが来なければならない.

性を失わない.

SE ステップの数の和と一致する. path の重みを weight \beta ; $w)$ とする.
テップの重みの積である. さらに, 長さ の path の重みの総和を$($

これは path を構成するス$n$weight $(\beta;w)$ ,$\mu_{n}^{\mathrm{D}}(\beta).--\sum_{1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)=2n}$は Catalan 数と表す. 例として, $\beta_{h}=1$ とおくとは $m$ -color super Catalan 数となる. また, この$\mu_{n}^{\mathrm{D}}(\beta)$(30)$(n=0,1,2, \ldots)$に, $\beta_{2h}=1,$ $\beta 2h+1=m$ とすると(こ対する母関数を$c_{n}$$\mu^{\mathrm{D}}(\beta)$$\mu_{n}^{\mathrm{D}}(\beta)$(31)$g^{\mathrm{D}}( \beta;z):=\sum_{n=0}^{\infty}\mu_{n}^{\mathrm{D}}(\beta)z^{n}$と定義する. 図 7 に重み付き Dyck path の例を示す.

: A weighted Dyck path with lengh(w)=10 and weight \beta ;$($$\text{図}7$$w)=(\beta_{1})^{2}(\beta_{2})^{2}\beta_{3}$

.

1B4

42

重み付き Motzkin path

ステップを加えて構成される格子路を Motzkin path と呼ぶ,
NE, SE ステップだけでなくステップについては図 8 参照. Motzkin path の長さ length(w) は NE, SE, ステップの数の和として定義される, Motzkin path の重み weight(b, $c;w$ ) は path を構成するステップの重みの積とする.

$\mathrm{E}$$\mathrm{E}$$\mathrm{E}$$.\mathrm{h}_{-\cdot\cdot---}^{l}\mathrm{i}|\mathrm{i}.\mathrm{i}1||$$.\mathit{1}^{1}\overline{\dot{}}---\cdot-\cdot.\cdot\sim\underline{\mathrm{i}j}$$arrow$

図 8: NE, SE and

以下では, NE ステップの重みを 1, 高さ
テップの重みを$\mathrm{c}_{h}$とする. さらに, 長さ$n$$\mu_{n}^{\mathrm{M}}(b,c)$$:= \sum_{1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)=n}$$\mu^{\mathrm{M}}(b, c)$

に対する母関数$g^{\mathrm{M}}(b, c;z)$$h$$\mathrm{E}$steps.

から始まる SE ステップの重みを$b\prime_{l}$

, 高さ

$h$

の

$\mathrm{E}$スの path の重みの総和を

weight $(b, c;w)$ ,$(n=0,1,2, .-. )$

,

(32)

を

(33)

$g^{\mathrm{M}}(b, c;z):= \sum_{n=0}^{\infty}\mu_{n}^{\mathrm{M}}(b, c)z^{n}$と表す. 図 9 は重み付き Motzkin path の一例である.

$\text{図}9$43: A weighted Motzkin path with length(u) $=10$ and weight(b,$\mathrm{c};w$)$=b_{1}b_{2}b_{3}c0(c_{1})^{2}c_{2}$.

重み付き Dyck path と連分数

Dyck path の解析において基本となるのは次の定理である.
定理 2. (Flajolet[4]) 列に対する母関数$\beta$によって重み付けられた Dyck path について, その組合せ論的量$g^{\mathrm{D}}( \beta;z)=\sum_{n=0}^{\infty}\mu_{n}^{\mathrm{D}}(\beta)z^{n}$$\mu^{\mathrm{D}}(\beta)$

は Stieltjes 型の連分数に展開される,

1$g^{\mathrm{D}}(\beta;z)=S(\beta;z):=$(34)$\beta_{1}z$1$1-\underline{\beta_{2}z}$1–$\cdot$..

1B5

証明. Dyck path は図 10 のように (a) 長さが 0 のものと (b) 長さが 2 以上 (NE ステップで始まる)のものに分類することができる.
を導入すると, 母関数$g^{\mathrm{D}}(\beta;z)$

ここで $\delta^{k}\beta=\delta(\beta_{1}, \beta_{2}, \cdots)=(\beta_{k+1}, \beta_{k+2})$

なるずらし演算子$\delta$は(35)$g^{\mathrm{D}}(\beta;z)=1+\beta_{1}z\mathrm{x}g^{\mathrm{D}}(\delta\beta;z)\mathrm{x}g^{\mathrm{D}}(\beta;z)$(36)$g^{\mathrm{D}}( \beta;z)=\frac{1}{1-\beta_{1}zg^{\mathrm{D}}(\delta\beta z)}$は図 10(b)と書ける. ここに (35) 式右辺第 1 項の 1 は長さ 0 の Dyck path, 右辺第 2 項のつのも 2
Dyck path に分は右の山に対応する. 同様にして,の左の山に対応し,$g^{\mathrm{D}}(\delta\beta;z)$$g^{\mathrm{D}}(\delta\beta;z)$$g^{\mathrm{D}}(\beta;z)$

けて考えることができる. この操作を繰り返すと,

1

1

(37)

$=\cdots$$=$$g^{\mathrm{D}}( \beta;z)=\frac{1}{1-\beta_{1}zg^{\mathrm{D}}(\delta\beta,z)}.=$$\beta_{1}z$$1- \frac{\beta_{1}z}{1-g^{\mathrm{D}}(\delta^{2}\beta z)}$

1$1- \frac{\beta_{2}z}{1-g^{\mathrm{D}}(\delta^{3}\beta z)}$口となり, 定理 2 は証明される

ゆ(a) Length 0.
図 10: Aclassification of Dyck paths,

44

重み付き Dyck path と Hankel 行列式

重みの総和のなす Hankel 行列式$\mu^{\mathrm{D}}(\beta)$$H_{k}^{(n)}(\beta)$$\mu_{n+2k-2(\beta)}^{\mathrm{D}}\mu_{n+k-1}^{\mathrm{D}}..\cdot(\beta)\mu_{n+k}^{\mathrm{D}}(\beta)|_{1}$$H_{k}^{(n)}(\beta):=|\mu_{n+i+j}^{\mathrm{D}}(\beta)|_{0\leq i,j\leq k-1}=|_{\mu_{n+k-1}^{\mathrm{D}}(\beta)}^{\mu_{n}^{\mathrm{D}}(\beta)}\mu_{n+1}^{\mathrm{D}}.\cdot.(\beta)$$\mu_{n+1}^{\mathrm{D}}.\cdot.(\beta)\mu_{n+2}^{\mathrm{D}}(\beta)\mu_{n+k}^{\mathrm{D}}(\beta)$

,

(38)

$(n=0,1,2, \ldots, k=0,1,2, \ldots)$について次のような組合せ論的な解釈が可能となる.
定理 3. (Viennot[12], Gessel-Viennot[5]) 列

組合せ論的量$\mu^{\mathrm{D}}(\beta)$

によって重み付けられた Dyck path について, そののなす Hankel 行列式の小行列式”$.\beta$$H(_{c1}^{r_{1\prime}},.\cdot.\cdot]^{r_{k}},^{\mathrm{C}k}$$\beta$)$:=|\mu_{r_{i}+c_{j}}^{\mathrm{D}}(\beta)|_{1\leq i,j\leq k^{7}}$$(0\leq r_{1}<\cdots<r_{k}, 0\leq c_{1}<\cdots<c_{k})$

(39)

1B6

は, グラフの重みの積憤として$H(_{c_{1}^{1}}^{r}$: : :: : :$c_{k}^{k}r\cdot$$\beta)=\sum_{\theta=(w_{1,..1},w_{k})\in^{\mathrm{d}}}$のように組合せ論的に表現できる. ただし,.
.

$\Theta^{\mathrm{d}}$weight$(\beta;w_{1})\cdots$

は, Dyck path の

$k$

(40)

weight $(\beta;wk)$

過小 $\theta=(w_{1}, \ldots, w_{k})$ で次の 2つの条件を満たすものの集合である.
$w_{i}$$k$

は $(-2r_{i}, 0)$ で始まり

個の Dyck path

で終わる長さ $2(r_{i}+c_{i})$ の Dyck path.

$(2\mathrm{q}., 0)$

は, どの相異なる Dyck path も節点を共有しない.

$w_{1},$ $\ldots,$ $w_{k}$図 11: An element of$\Theta^{\mathrm{d}}$.

証明. 行列式の定義より$H(_{\mathrm{c}_{1},\ldots,c_{k}}^{r_{1},\ldots,r_{k}}$;$\beta)=\sum_{\sigma\in\dot{4}\overline{\mathrm{J}}_{k}}$sign(\sigma )sign (a) weight !;$\sum$$=$...

$\mu_{r_{1}+c_{\sigma(1)}}^{\mathrm{D}}(\beta)\mu_{r_{2}+c_{\sigma(2)}}^{\mathrm{I})}(\beta)$$w_{1})$$($

weight$\mu_{r_{k}+c_{\sigma(k)}}^{\mathrm{D}}.(\beta)$$(\beta;w_{2})\cdots$

weight $(\beta;wk)$$\xi=(\sigma\theta))\in\equiv$

と書ける.

ここで,

$\theta=(w_{1}, \ldots, w_{k})$る.

このとき, 三$\mathrm{d}$$\dot{\grave{\mathrm{L}}}^{\gamma}‘ k$

は $\{1, 2, \ldots, k\}$ の置換の集合,

三は置換

三は三 $:=$ {(b た,の対の集合, 宮三一の余集合上の全単射 : 三一三$\mathrm{d}$’$\mathrm{d}arrow$$\theta)|\theta\in\ominus^{\mathrm{d}}$$\mathrm{d}arrow$$\overline{=}^{\mathrm{d}}$$\phi$$\xi’=\phi(\xi),$ $\xi=(\sigma, \theta=(w_{1}, \ldots, w_{k})),$$\xi’=(\sigma’,$$\sigma\in \mathrm{t}\supset\backslash k$と Dyck path の

$k$

個組

} (妬恒等置換) を表しているとすで, 次の性質を持つものを構成できる.

$\theta’=(w_{1}’, \ldots, w_{k)}^{\prime\backslash })$とすると,$\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(\sigma)=-\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(\sigma’)$$\{$weight
この集合三$—-\mathrm{d}$$(\beta;w_{1})\cdots$

は Dyck path のweight $(\beta;w_{k})=$ weight$k$$(\beta;w_{1}’)\cdots$

weight$(\beta;w_{k}’)$.

個組の中で少なくとも 2 組が交わるような集合となっている.

path の組合せの集合三を$H(_{c_{1},\mathrm{c}_{k}}^{r_{1\prime}\ldots’ r_{k}} \ldots,; \beta)=(\xi\sum_{\in_{-}^{-}-\mathrm{d}}+\xi\in\overline{--}---\sum_{-\mathrm{d}})$のように 2 つに分けると, 全単射$H(_{\mathrm{c}}^{r}$となる.

: : ::: : ;$\phi$

sign$(\sigma)$

weight$(\beta;w_{1})$weight$(\beta;w_{2})$–weight$(\beta;w_{k})$(41)の性質より右辺第 1 項は消えるので,$c_{k}r_{k}$$\beta)=\sum_{\theta\in\Theta^{\mathrm{d}}}$weight$(\beta;w_{1})$–weight$(\beta;w_{k})$

口

167

系 2. 定理 3 より,$H_{k}^{(0)}(\beta),$ $H_{k}^{(1)}(\beta)$に対応する Dyck path の$k$

個組はそれぞれ 1 つだけ存在し,図 12 のようになる. よって$H_{k}^{(0)}( \beta)=\prod_{i=1}^{k-1}(\beta_{2i-1}\beta_{2i})^{k-i}$,$H_{k}^{(1)}( \beta)=(\beta_{1})^{k}\prod_{i=1}^{k^{-}-1}(\beta_{2i}\beta_{2i+1})^{k-\mathrm{i}}$,$(k=0,1,2, \ldots)$(42)が成り立つ.

$\prod \mathrm{K}12$45: Geometrical representations of the Hankel determinants with tuples of Dyck paths.

$\mathrm{q}\mathrm{d}$

アルゴリズ

重みの列

$\beta,$$\beta’$$\Delta$のグラフ論への応用

に対して母関数$g^{\mathrm{D}}(\beta;z)$

が

(43)

$g^{\mathrm{D}}( \beta;z)=\sum_{n=0}^{\infty}\mu_{n}^{\mathrm{D}}(\beta)z^{n}=1+\beta_{1}zg^{\mathrm{D}}(\beta’;z)$なる関係式を満たしているとする. ある定められた定義より, 存在する場合は, 一意に定まる.

$\mathrm{q}\mathrm{d}$$\beta$に対して関係式 (43) を満たす$\beta’$は母関数のアルゴリズムのグラフ論的な解釈として次の定理が成り立つ.
定理 4. (Viennot[12]) Dyck path をの必要十分条件は,$\mathrm{q}\mathrm{d}$$\text{重}i\star$付ける 2 つの列$\beta_{0}’=0$と

力 , 上の関係式 (43) を$1\mathrm{t}$$\beta’$$?\ovalbox{\tt\small REJECT}\backslash _{\llcorner}^{arrow}$

すためアルゴリズムの漸化式$\beta_{2h+1}+\beta_{2h+2}=\beta_{2h}’+\beta_{2h+1}’$

ただし,$\beta$,,$\beta_{2\mathrm{h}}\beta_{2\mathrm{h}+1}=\beta_{2h-1}’\beta_{2h}’$(44)が成り立つことである.

証明. (i) Dyck path から Motzkin path への変換 (contractlon)

Dyck path
length(w) $=2n$weighted by
$w$

$\{$

$arrow T$$\beta’$

$\{$

$T$

:

Motzkin path $T(w)$length(T(w)) $=n$weighted by $(b’,c’)$を考える, ここで変換 $T$ として図 13 に表される変換を考え, Motzkin path$b_{h}’=\beta_{2h-1}’\beta_{2h}’$,$c_{h}’=\beta_{2h}’+\beta_{2h+1}’$$T(w)$ の重み $(b’, c’)$ を

188とする. このとき, Dyck path と Motzkin path $T(w)$ について

weight$\{$$(b’,c’;w^{\mathrm{M}})= \sum_{T(w^{\mathrm{D}})=w^{\mathrm{b}4}}$

weight$(\beta’;w^{\mathrm{D}})$(45)$(n=0,1,2, \ldots)$$\mu_{n}^{\mathrm{M}}(b’, c’)=\mu_{n}^{\mathrm{D}}(\beta’\rangle,$$g^{\mathrm{M}}(b’,c’;z)=g^{\mathrm{D}}(\beta’;z)$が成り立つ.

図 13: The contraction $T$ .

(ii) 次に Dyck path の Motzkin path への変換

Dyck path
length(w) $=2n(n\geq 1)$
weighted byとして$T^{+}$

Motzkin path $T(w)$

$w$

$\{$

$arrow T^{+}$$\{$$\beta$を考える. ここで変換$T^{+}$$-.\sim\backslash \backslash \backslash \backslash$length(T(w)) $=n-1$
weighted by $(b,c)$は図 14 に表される変換とし, Motzkin path$b_{h}=\beta_{2h}\beta_{2h+1}$,$’[perp]^{T^{1}+}(w)$の重み $(b, c)$ を$ch=\beta_{2h+}\iota+\beta_{2h+2}$(46)とする. このとき, Dyck path と Motzkin path $T^{+}(w)$ の間に$\beta_{1}$$\{$weight$(b, c;w^{\mathrm{M}})= \sum_{T(w^{\mathrm{D}})=w^{\mathrm{M}}}$$\beta_{1}\mu_{n-1}^{\mathrm{M}}(b,c)=\mu_{n}^{\mathrm{D}}(\beta’)$,weight$(\beta;w^{\mathrm{D}})$$(n=1,2, , \ldots)$(47)$1+\beta_{1}zg^{\mathrm{M}}(b,c;z)=g^{\mathrm{D}}(\beta;z)$なる関係式が成り立つ.

(i)(ii) より$b_{h}=\beta_{2h}\beta_{2h+1}$,$c_{h}=\beta_{2h+1}+\beta_{2h+2}$$\Rightarrow$$g^{\mathrm{D}}(\beta;z)=1+\beta_{1}zg^{\mathrm{M}}(b,c;z)$$b_{h}’=\beta_{2h-1}’\beta_{2h}’$,$c_{h}’=\beta_{2h}’+\beta_{2h+1}’$$\Rightarrow$$g^{\mathrm{M}}(b’,c’;z)=g^{\mathrm{D}}(\beta’).z)$

(48)

$\{$

1B9

図 14: The contraction$T^{+}$

.

が言える.

(iii)

$\mathrm{q}\mathrm{d}$アルゴリズムの白化式$\beta_{2h+1}+\beta_{2h+2}=\beta_{2h}’+\beta_{2h+1}’$,$\beta_{2h}\beta_{2h+1}=\beta_{2h-1}’\beta_{2h}’$が成立しているとき. (48) より$b=b’$ ,$c=c’$$g^{\mathrm{M}}(b, \mathrm{c};z)=g^{\mathrm{M}}(b’, c’;z)$$g^{\mathrm{D}}(\beta;z)=1+\beta_{1}zg^{\mathrm{D}}(\beta’;z)$

となる.

一意性より

$\mathrm{q}\mathrm{d}$アルゴリズムの漸化式 (44) は (43) が成り立つための必要+分条件となる

口と捉えることができる. 以下, 初期
アルゴリズムの定理 3 より, (43) は母関数を用いたと表す.
をアルゴリズムの 1 反復
として
, 境界値
値
アルゴリズムで反復計算したものとする. このとき, (43) より
回からは$\text{表}\xi \mathrm{E}$$\mathrm{q}\mathrm{d}$$\beta_{0}^{(n)}=0$$\beta^{(0)}=\beta$$\beta$$n$$\betaarrow\beta’$$\beta^{(0)}arrow\beta^{(1)}$$\beta^{(n)}$$\mathrm{q}\mathrm{d}$$\mathrm{q}\mathrm{d}$$g^{\mathrm{D}}(\beta;z)$となり, 長さ $n$ の Dyck path の重みの総和$\mu_{n}^{\mathrm{D}}$(\beta 戸よ$\mu_{n}^{\mathrm{D}}(\beta)=\beta_{1}^{(0)}\beta_{1}^{(1)}\cdots\beta_{1}^{(n-1)}$$\mathrm{q}\mathrm{d}$,アルゴリズムの変数を肺 1 て$(n=0,1,2, \ldots)$

(49)

170

と表される. また, Hankel 行列式

についても,$H_{k}^{(n)}(\beta)$$H_{k}^{(0)}( \beta^{(n)})=\prod_{i=1}^{k-1}(,\theta_{2i-1}^{(n)}\beta_{2i}^{(n)})^{k-i}$

,

(50)

$\mu_{n+k}^{\mathrm{D}}(\beta)=\mu_{n}^{\mathrm{D}}(\beta)\mu_{k}^{\mathrm{D}}(\beta^{(n)})$

より

(51)

$H_{k}^{(n)}( \beta)=(\prod_{i=0}^{n-1}\beta_{1}^{(\mathrm{t})})^{k}\prod_{j=1}^{k-1}(\beta_{2\mathrm{j}-1}^{(n)}\beta_{2j}^{(n)})^{k-j}$となる. これらは, グラフ論的量である$\mu_{n}^{\mathrm{D}}(\beta)$や$H_{k}^{(n\}}(\beta)$が$\mathrm{q}\mathrm{d}$アルゴリズムを用いて計算可能であることを示している.

5$\mathrm{F}\mathrm{G}$アルゴリズムと Schr\"oder path

前節でみたように$\mathrm{q}\mathrm{d}$アルゴリズムと Dyck path には密接な関係が存在する.

$\mathrm{q}\mathrm{d}$アルゴリズムの 1 点 Pade 近似の計算アルゴリズムである.

本節では, 2 点
アルゴリズムのグラフ論的
Pade 近似の計算アルゴリズムである
アルゴリズムを取り上げ,アルゴリズムと Schr\"oder path について, 前節と同様の議論が成り立つことを意味を考察して,報告する.
は $z=0$ の周りでの母関数$g^{\mathrm{D}}(\beta;z)$$\mathrm{F}\mathrm{G}$$\mathrm{F}\mathrm{G}$$\mathrm{F}\mathrm{G}$51

重み付き Schr\"oder path

NE, SE ステップ, および, 図 15 のいう.

ステップによって構成される格子路を Schr\"oder path と$\mathrm{E}\mathrm{E}$.

$\overline{i}.\cdot..\mathit{1}_{\vee---}^{1}.||\mathrm{i}$$.\cdots \mathrm{h}_{------}^{\dot{\mathrm{i}}}’|\mathrm{i}1|\ldots.!|$,$\underline{\mathrm{t}}$図 15: NE, SE and EE steps.

以下, Dyck path のときと同様に高さ
重み$\beta_{h},$プの数)$\mathrm{E}\mathrm{E}$$+2\mathrm{x}$ステップには重み($\mathrm{E}\mathrm{E}$$\gamma_{h}$$h$から始まる NE ステップには重み 1, SE ステップにはが付いているとする. path の長さ length(w) は$/\mathrm{s}\mathrm{E}\backslash$’NE ステッステップの数) とし, path の重みは path を構成するステップの重みの積とする,

また, 長さ $n$ の path の重みの総和を$\mu_{n}^{\mathrm{S}}(\beta, \gamma)$$:= \sum_{\mathrm{I}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)=n}$weight$(\beta,\gamma jw)$,$(n=0,1,2, \ldots)$と表す. 図 16 に Schr\"oder path の一例をあげる. $\beta_{h}=1,\gamma_{h}=w-1$ として得られる(52)$\mu_{n}^{\mathrm{S}}(\beta,\gamma)$

は3.1 節の Narayana 多項式 $N_{n}(w)$ に一致し, Schr\"oder pat 旧こ関連する組合せ論的数の例となっている.

52

重み付き Schr\"oder path と連分数

Schr\"oder path$\mathrm{s}$に対して, 最初のステップが NE, 最後のステップが SE であり, かつ始点と終点以外に高さ 0 とならない Schr\"oder path$\mathrm{S}*$を考える. NE ステップの重みを 1, 高さ $h+1$ から

171

図

16: A weighted Schr\"oder path weighted by$(\beta_{1})^{2}(\beta_{2})^{2}\beta_{3}\gamma_{1}\gamma_{2}$$1e,\mathrm{n}\mathrm{g}\mathrm{h}(w)=12,$$(\beta, \gamma),$weight(\beta ,\gamma ;w)$=$.

始まる SE ステップの重みを$\mathrm{E}\mathrm{E}$$\beta_{h}^{*},$

ステップの重みを$\beta_{0}^{*}=\frac{1}{\gamma_{0}}$,$\beta_{k}^{*}=\frac{\beta_{k}}{\gamma_{k-1}\gamma_{k}}$なる重みの関係式を満たすとする. さらに, 長さ$\mu_{n}^{\mathrm{S}}(\beta, \gamma):=\sum_{1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)=n}$とし,$\gamma_{h}^{*}$,

weightの重み$\gamma_{k}^{*}=\frac{1}{\gamma_{k}}$の path$n$$\mathrm{S}$

を用いて

(53)

.

の重みの総和を$\mathrm{S}*$$(\beta^{*}, \gamma^{*} ; w)$$(\beta, \gamma)$,$(n=1,2, \ldots)$(54)と負の添字を用いて表す.
この時, Dyck path についての Flajolet の定理 (定理 2) の類似が成り立つ.
定理 5. 列$(\beta, \gamma)$

によって重み付けられた Schr\"oder path について, その組合せ論的量$\mu^{\mathrm{S}}(\beta, \gamma)$に対する母関数$g^{\mathrm{S}}( \beta, \gamma;z)=\sum_{n=0}^{\infty}\mu_{n}^{\mathrm{S}}(\beta)z^{n}$,$g^{\mathrm{S}*}( \beta,\gamma;z)=-\sum_{n=-\infty}^{-1}\mu_{n}^{\mathrm{S}}(\beta)z^{n}$(55)

は, T-連分数の形に展開され,$g^{\mathrm{S}}(\beta, \gamma;z)=T(\beta, \gamma;z)$,$g^{\mathrm{S}*}(\beta, \gamma;z)=T(\beta_{1}\gamma;z)$

1

(57)

$T(\beta, \gamma;z):=$$\beta_{1}z$$1-\gamma_{0}z-$$\beta_{2}z$$1-\gamma_{1}z-$$1-\gamma_{2}z-\cdot$

となる.

(56)

..

172

53

重み付き Schr\"oder path と Toeplitz 行列式

path の重みの総和$\mu^{\mathrm{S}}(\beta, \gamma)$のなす Toeplitz 行列式$T_{k}^{(n)}(\beta, \gamma)$

:

(58)

$T_{k}^{(n)}(\beta_{1}\gamma):=|\mu_{n-i+j}^{\mathrm{S}}(\beta, \gamma)|_{0\leq i,j\leq k-1}$$\mu_{n}^{\mathrm{S}}(\beta,\gamma)$$\mu_{n+1}^{\mathrm{S}}(\beta, \gamma)$$\mu_{n+k-1}^{\mathrm{S}}(\beta,\gamma)$$\mu_{n-1}^{\mathrm{S}}(\beta)\gamma)$$\mu_{n}^{\mathrm{S}}(\beta,\gamma)$$\mu_{n+k-2}^{\mathrm{S}}(\beta,\gamma)$

.

.

.

$\mu_{n-k+1}^{\mathrm{S}}(\beta_{1}\gamma)$

(59)

.

.

.

$\cdot$$\cdot$$\cdot$$\mu_{n}^{\mathrm{S}}(\beta,\gamma)$$\mu_{n-k+2}^{\mathrm{S}}(\beta,\gamma)$$(n=0, \pm 1, \pm 2, \ldots, k=0,1,2, \ldots)$について, Dyck path に対する Viennot の第 1 定理 (定理$3\rangle$の系と同様に, 以下が成り立つ. (証明は図 17 を利用して行われる).
定理 6. Toeplitz 行列式は連分数の係数を用いて,$T_{k}^{(0\rangle}( \beta, \gamma)=(-1)2\prod_{i=1}^{k-1}\underline{k}\mathrm{L}^{k}-A1(\frac{\beta_{?}}{\gamma_{i-1}}.)^{k-i}$,$T_{k}^{(-1)}( \beta,\gamma)=(-1)^{\frac{k\langle k-1\rangle}{2}}(\gamma_{0}^{*})^{k}\prod_{i=1}^{k-1}(\frac{\beta_{i}^{*}}{\gamma_{i-1}^{*}})^{k-i}$$(k=0,1,2, \ldots)$(60)と表される.

–: ‘’Normal” Schr\"oder path$\mathrm{E}*]17:$$—\sim$: “Tw .o–legged”Schr\"oder path

Geometrical representations of the Toeplitz determinants with tuples of Schr\"oder paths.

173

54
$\mathrm{F}\mathrm{G}$$\mathrm{F}\mathrm{G}$アルゴワズ\Delta の組合せ論への応用

アルゴリズム (cf. [6, 8]) は関数の原点と無限遠点における 2 点 Pade 近似を Te 連分数の形で与えるためのアルゴリズムであり, その漸化式は$F_{k+1}^{(n)}.+G_{k}^{\langle n\rangle}=F_{k}^{(n+1)}+G_{k}^{(n+1)}$$\ovalbox{\tt\small REJECT})$

$=0$

,

で与えられる. 添字をみると$G_{0}^{(n)}= \frac{c_{n}}{c_{n-1}}$$\mathrm{q}\mathrm{d}$離散時間可積分系とみなせる.
を用いた$\mathrm{F}\mathrm{G}$,,$F_{k+1}^{\langle n)}G_{k+1}^{(n+1)}=F_{k+1}^{(n+1)}G_{k}^{(n)}$$(n=0, \pm 1, \pm 2, \ldots, k=0,1,2, \ldots)$

アルゴリズムとの違いは明らかであるが,$\mathrm{q}\mathrm{d}$,$\mathrm{F}\mathrm{G}$アルゴリズムもまた

アルゴリズムと Dyck path の場合と同様の議論により, 母関数

アルゴリズムの表現として$g^{\mathrm{S}}(\beta,\gamma;z)=1+(\beta_{1}+\gamma_{0})zg^{\mathrm{S}}(\beta’, \gamma’;z)$

(61)

$\{$

$g^{\mathrm{S}*}(\beta,\gamma;z)=1+(\beta_{1}+\gamma_{0})zg^{\mathrm{S}+}(\beta’, \gamma^{J};z)$$g^{\mathrm{S}}(\beta’,\gamma’;z)=-\langle\gamma_{0}’)^{-1}z^{-1}+(_{\backslash }\gamma_{0}’)^{-1}z^{-1}g^{\mathrm{S}}(\beta, \gamma;z)$

(62)

$\{$

$g^{\mathrm{S}*}(\beta’, \gamma’;z)=-(\gamma_{0}’)^{-1}z^{-1}+(\gamma_{0}’)^{-1}z^{-1}g^{\mathrm{S}+}(\beta,\gamma;z)$が得られる. ここに,$(\beta, \gamma)rightarrow(\beta’, \gamma’)$は$\mathrm{F}\mathrm{G}$アルゴリズムの 1 反復に対応している. Viennot の第2 定理 (定理 4) の類似として以下が証明される.
定理 7. Schr\"oder path を重み付ける 2 つの列の組$(\beta, \gamma)$と$(\beta’, \gamma’)$が, 上の関係 (61), (61) を満たすための必要十分条件は, 次が成り立つことである.
$\beta_{h+1}+\gamma_{h}=\beta_{h}’+\gamma\neq 0$

ただし,$\beta_{0}’=0$,$\beta_{h+1}\gamma_{h+1}’=\beta_{h+1}’\gamma_{h}$,$(h=0,1,2, \ldots)$

(63)

.

アルゴリズムを用いると組合わせ論的素量が計算可能となる. とりわけ, path の重み
が全て 1 であるとき, path の重みの総和は条件を満たす path の本数の数え上げになっていること$\beta_{h},$$\mathrm{F}\mathrm{G}$に注意する. ここでは結果のみ記す.

path の重みの総和$\mu^{\mathrm{S}}(\beta, \gamma)$

について$\prod_{i=1}^{|n|}\gamma_{0}^{(i)}$,$(n=0,1,2, \ldots)$$\mu_{n}^{\mathrm{S}}(\beta, \gamma)=\{$$\prod_{i=0}^{|n|-1}$が成り立つ. また, Toeplitz 行列式$T_{k}^{(n)}(\beta, \gamma)$$\gamma_{0}^{*}(-i)$

は$\mathrm{F}\mathrm{G}$,$(n=-1, -2, \ldots)$

アルゴリズムの係数を用 4 て$T_{k}^{(n)}( \beta, \gamma)=(\mu_{n}^{\mathrm{S}}(\beta, \gamma))^{k}\prod_{i=1}^{k-1}(-\frac{\beta_{i}^{(n)}}{\gamma_{i-1}^{(n\rangle}})^{k-i}$と表わされる.

$\gamma_{h}$

174

6

おわりに

本稿の前半では半無限, 無限戸田方程式のタウ関数と直交多項式論に基づいて, 種々の組合せ論
アルゴ的数のなす Hankel 行列式を導出した. 後半では可積分系のグラフ論的な解釈を考察し,リズムとアルゴリズムを通じて, path の重みの総和がこれらの離散可積分系のタウ関数として計算されることを示した. 本研究により, 戸田型可積分系の特殊解と個々の組合せ論的数やグラフ$\mathrm{q}\mathrm{d}$$\mathrm{F}\mathrm{G}$との対応が明らかになった. しかし, 未だ可積分系のグラフ論的な全体像は見えてはいない. 新し

い分野であり, 今後この方面の研究が大きく発展することを願いたい 4

参考文献[1] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A87(1999), 33-51.
[2] A. I. Aptekarev, A. Branquinho and F. Marcellan, Toda-type differential equations for the reccurComput. APPI Math,rence coefficients of orthogonal polynomials and Reud transformation,
78(1997), 139-160.
[ T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordan and Breach, New York, 1978$\mathrm{J}$$3|$

P. Flajolet, Combinatorial aspects of continued fractioms, Discrete Math, 58(1980), 125-161.
Viennot, Binomial determinants, paths and hook length formulae, Adv. in Math,[5] I. Gessel and[$4|$$\mathrm{G}_{-}$

58(1985), 300321[6] W. B. Jones and W. J. Thron, Padi and Rational Apprommation, Academic Press, NewYork, 1977,
pp 163-171.
[7] K. Kajiwara, T. Masuda, M. Noumi, Y. Ohta and Y. Yamada, Determinant formulas for the Toda
and discrete Toda equations, Funkcialaj Ekvacioj, 44(2001), 291-307.
[8] J. H. McCabe, A formal extension of the Pade table to include two point Pade quotionts. J. Inst.
Math Appl. 15(1975), 363-372.
[9] Y. Nakamura and A. Zhedanov, Special solutions of the Toda chain and combinatorial numbers, J.
Phys. , Math. Gen. 37(2004), 5849-5862; 中村, 組合せ論的整数のなす Hanke4 行列式, 数学会 2002
秋季総合分科会, 無限可積分系セッション, 島根大学 中村, 大平, A. Zhedanov, 組合せ論的数のなす
Hankel 行列式と戸田方程式の変数分離解, 数学会 2004 年度年会, 無限可積分系セッション, 筑波大学.
$\mathrm{A}$$j$$|10|$

大平, 中村, 一般化された Catalan 数のなす Hankel 行列式と戸田方程式, 数学会 2004 年度年会, 無限可積分系セッション, 筑波大学.

$|11]\mathrm{F}_{\sim}$

Peherstorfer, On Toda lattices and orthogonal polynomials, J. Comput. Appl. Math. 133(2001),

519-534.
[12] X. G. Viennot, A com binatorial interpretation of the quotient-difference algorithm, Formal Power
Sertes and Algebraic Cornbinatorics (Moscow, 2000), Springer-Verlag, Berlin, 2000, . 379-390.
$\mathrm{P}\mathrm{P}$