非交叉径路の数え上げ問題

上岡 修平

上岡 修平私の研究分野は離散力学系と数え上げ組合せ論です。特に両者の間の関係を明らかにすることで、「数え上げ組合せ論の問題を、離散力学系の手法を用いて解く」、「離散力学系の持つ諸性質を、組合せ論や離散数学の道具を用いて解析する」ことを目的に、研究を進めています。ここでは私が考察対象としている数え上げ組合せ論の問題に関して、簡単な例を交えつつ解説します。

数え上げ組合せ論は、組合せ数学の一分野で、その主題は、ものの数を数えることにあります。つまり与えられた有限集合に対して、その元の数(有限集合の位数)を求めることが目的です。趣旨はとても単純です。

例1:碁盤上で、路(黒線)を辿って道をつくることを考える。与えられた碁盤上の二つの目(黒線の交点)「U」と「V」に対して、「U」から「V」へと至る道筋は何通りあるか。ただし遠回りをしてはいけない。

これは、数え上げ組合せ論の問題の中でも、最も典型的かつ初等的なものの一つです。二項係数(階乗)を使って厳密解を書き下すことができます。次の例はより複雑です。

例2:正方格子の上に、n 本の径路を描くことを考える。与えられた2n 個の格子点「U1」「U2」…「Un」と「V1」「V2」…「Vn」に対して、「U1」から「V1」へと至る径路、「U2」から「V2」へと至る径路、…、「Un」から「Vn」へと至る径路をそれぞれ描く。ただし、次の二つの条件を守らなければならない。
(a)遠回りをしてはいけない。
(b) どの二本の径路も交叉してはいけない(同じ格子点を通ってはいけない)。

この問題は、例1の初等的な数え上げ問題に対する拡張を与えています。例1と比較して径路の数はn 本に一般化され、さらに径路の非交叉条件⒝が新たに追加されています。問題を本質的に難しくしているのは条件⒝の方です。(特定の「Ui」「Vi」の選び方に対しては、厳密解が知られています。)

非交叉径路の数え上げ問題例2のような問題は、非交叉径路の数え上げ問題と呼ばれ、近年、数学や物理学の多くの分野で注目を集めています。例えば数学では、表現論のSchur関数に対する数え上げ公式が有名です。また統計物理学では、vicious walkers または非衝突性ランダムウォークなどの呼び名で同様の研究がなされています。特にこの分野では、分配関数の計算などで、非交叉径路の計数が要求されます。

私が考察対象としているのは、例2のような、非交叉径路の数え上げ問題です。正方格子の場合に限らず、三角格子や籠目格子など様々なグラフに対して適用できる計算法の構築を目論んでいます。そのために離散可積分系と呼ばれる離散力学系の構造を利用するのですが、紙数の都合上、詳細は割愛させて頂きます。

(助教・情報学研究科数理工学専攻)