数学において自然数 n に対するモツキン数(モツキンすう、: Motzkin number)とは、円周上の相異なる n 個の点を互いに交わらないような線分で結ぶ方法の数である。点は互いに区別がつき、また結ばれていない点があってもよい。名称はテオドール・モツキン英語版ドイツ語版にちなむ。モツキン数は幾何学組合せ数学数論といった分野に多様な応用がある。

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

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, ... (オンライン整数列大辞典の数列 A001006

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

 

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

 

性質

編集

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

 

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

 

モツキン素数(Motzkin prime)は素数であるようなモツキン数である。2013年 (2013-October)現在、4個のモツキン素数が見つかっている。

2, 127, 15511, 953467954114363 (オンライン整数列大辞典の数列 A092832

組合せ数学的な解釈

編集

n に対するモツキン数は、次の条件を満たす長さ n − 1正整数列の数に等しい。

  • 初項と末項は1または2であり、隣接する2項間の差は −1, 0, 1 のいずれかである。

また、次の条件を満たす長さ n + 1 の正整数列の数にも等しい。

  • 初項と末項は1であり、隣接する2項間の差は −1, 0, 1 のいずれかである。

さらに、2次元デカルト座標平面において次の条件を満たす経路の数にも等しい。

  • (0, 0) から出発し (n, 0) まで到達する。
  • 経路は、座標が両方とも非負整数である点(格子点)のみを結んだ折れ線になっている。
  • ある格子点からその次の格子点へ向かう位置ベクトルは (0,1), (1,1), (1, −1) のいずれかである。

例えば、次の図は (0, 0) から (4, 0) へ到達する9通りのモツキン経路を示す。

 

数学の諸分科にわたって、モツキン数には少なくとも14通りの相異なる定義方法がある(このカウントはサーベイDonaghey & Shapiro (1977) による)。Guibert, Pergola & Pinzani (2001)vexillary involution英語版の数がモツキン数を使って数えられることを示した。

関連項目

編集

参考文献

編集
  • Bernhart, Frank R. (1999), “Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics 204 (1-3): 73–112, doi:10.1016/S0012-365X(99)00054-0 
  • Donaghey, R.; Shapiro, L. W. (1977), “Motzkin numbers”, Journal of Combinatorial Theory, Series A 23 (3): 291–301, doi:10.1016/0097-3165(77)90020-6, MR0505544 
  • Guibert, O.; Pergola, E.; Pinzani, R. (2001), “Vexillary involutions are enumerated by Motzkin numbers”, Annals of Combinatorics 5 (2): 153–174, doi:10.1007/PL00001297, ISSN 0218-0006, MR1904383 
  • Motzkin, T. S. (1948), “Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products”, Bulletin of the American Mathematical Society 54 (4): 352–360, doi:10.1090/S0002-9904-1948-09002-4 

外部リンク

編集