モツキン数

数学において自然数  に対するモツキン数（モツキンすう、）とは、円周上の相異なる  個の点を互いに交わらないような線分で結ぶ方法の数である。点は互いに区別がつき、また結ばれていない点があってもよい。名称はにちなむ。モツキン数は幾何学、組合せ数学、数論といった分野に多様な応用がある。

 に対するモツキン数  は以下のとおりである。

 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... （）

 例 

次の図は、円周上の 4 個の点を互いに交わらないように結ぶ 9 通りの弦の引き方を示す（）。

Image:MotzkinChords4.svg

次の図は、円周上の 5 個の点を互いに交わらないように結ぶ 21 通りの弦の引き方を示す（）。

Image:MotzkinChords5.svg

 性質 

モツキン数は次の漸化式を満たす。

モツキン数は二項係数とカタラン数を使って書くことができる（  は床関数）。

モツキン素数（Motzkin prime）は素数であるようなモツキン数である。、4個のモツキン素数が見つかっている。

 2, 127, 15511, 953467954114363 （）

 組合せ数学的な解釈 

 に対するモツキン数は、次の条件を満たす長さ  の正整数列の数に等しい。
 初項と末項は1または2であり、隣接する2項間の差は −1, 0, 1 のいずれかである。

また、次の条件を満たす長さ  の正整数列の数にも等しい。
 初項と末項は1であり、隣接する2項間の差は −1, 0, 1 のいずれかである。

さらに、2次元デカルト座標平面において次の条件を満たす経路の数にも等しい。
 (0, 0) から出発し (, 0) まで到達する。
 経路は、座標が両方とも非負整数である点（格子点）のみを結んだ折れ線になっている。
 ある格子点からその次の格子点へ向かう位置ベクトルは (0,1), (1,1), (1, −1) のいずれかである。
例えば、次の図は (0, 0) から (4, 0) へ到達する9通りのモツキン経路を示す。

Image:Motzkin4.svg

数学の諸分科にわたって、モツキン数には少なくとも14通りの相異なる定義方法がある（このカウントはサーベイ による）。 は の数がモツキン数を使って数えられることを示した。

関連項目




参考文献





外部リンク


Category:数論
Category:素数
Category:組合せ論
Category:整数の類
Category:数学に関する記事
Category:数学のエポニム