格子経路組合せ理論の研究

格路径组合理论研究

基本信息

批准号：
06640329
负责人：
佐藤優子
金额：
$ 0.83万
依托单位：
Osaka Prefecture University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06640329/
关键词：
組合せ理論格子経路カタラン数母関数正則表現

项目摘要

本研究では、多次元空間で2つの平行超平面で制限される格子経路の組合せ論的解析を行い、下記の結果を得た:超平面の方程式に含まれる係数が有理数である場合、2つの平行超平面で制限される格子経路の個数に関する母関数は、関数行列表示による多変数の有理関数で与えられている。関数行列を構成する項(基本関数列)は、第2種Chebyshev多項式を一般化した多変数の多項式であるが、本研究では、この基本関数列の性質を詳しく調べ、その漸化式等の関係式を得た。次に母関数に含まれる関数行列の逆行列の性質を調べたが、具体的な成果は得られていない。格子経路は、Stackやplanted plane treeの問題に限らず離散構造をもつ種々の組合せ問題に現れる。本研究では、計算機科学の基礎である正則言語の帰納推論の問題、特に計算量の問題を取り上げ、そこで生じた組み合わせ問題が格子経路問題に関連することがわかった。正則言語はすべてword上の正則表現で表すことが出来ることが知られている。この表現に出現するwordのすべてのheadが異なる場合、可能な正則表現の個数はCatalan数を用いて与えられることがわかった。Catalan数は2次元空間の格子経路で原点を通る傾きが1の直線で制限される格子経路の個数である。一般のword上の正則表現は一般化されたCatalan数を用いて表現できると思われるが、現在引き続きこの研究を行っている。

在这项研究中，我们对多维空间中的两个平行超平面限制的晶格路径进行了结合分析，并获得了以下结果：当超平面方程中包含的系数是有理数时，则基于两个平行超平面函数限制了lattice路径的源函数。构成函数矩阵的术语（基本函数序列）是多个多项式的术语，可以推广第二种类型的Chebyshev多项式。在这项研究中，我们详细研究了该基本函数序列的特性，并获得了一个关系方程，例如其复发方程。接下来，我们研究了源函数中包含的函数矩阵的反矩阵的属性，但没有获得具体结果。晶格路径出现在各种与离散结构的组合问题中，而不仅仅是堆栈和种植的平面树问题。这项研究解决了常规语言的归纳推理问题，这是计算机科学的基础，尤其是计算的复杂性，发现出现的组合问题与晶格路径问题有关。众所周知，所有普通语言都可以在单词上以正则表达方式表示。已经发现，如果该表达式中出现的单词的所有头部都不同，则使用加泰罗尼亚数字给出了可能的正则表达式数量。加泰罗尼亚州的数量是二维空间中的晶格路径数量，该晶格路径受到直线的限制，坡度为1穿过原点。据信，可以使用广义加泰罗尼亚数字表示一般单词的正则表达式，但目前正在进行这项研究。