モツキン数
数学において自然数 テンプレート:Mvar に対するモツキン数（モツキンすう、テンプレート:Lang-en-short）とは、円周上の相異なる テンプレート:Mvar 個の点を互いに交わらないような線分で結ぶ方法の数である。点は互いに区別がつき、また結ばれていない点があってもよい。名称はテンプレート:仮リンクにちなむ。モツキン数は幾何学、組合せ数学、数論といった分野に多様な応用がある。
に対するモツキン数 は以下のとおりである。
- 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, ... （テンプレート:OEIS）
例
次の図は、円周上の 4 個の点を互いに交わらないように結ぶ 9 通りの弦の引き方を示す（テンプレート:Math）。
次の図は、円周上の 5 個の点を互いに交わらないように結ぶ 21 通りの弦の引き方を示す（テンプレート:Math）。
性質
モツキン数は次の漸化式を満たす。
モツキン数は二項係数とカタラン数を使って書くことができる（ は床関数）。
モツキン素数（Motzkin prime）は素数であるようなモツキン数である。テンプレート:Asof、4個のモツキン素数が見つかっている。
- 2, 127, 15511, 953467954114363 （テンプレート:OEIS）
組合せ数学的な解釈
テンプレート:Mvar に対するモツキン数は、次の条件を満たす長さ テンプレート:Math の正整数列の数に等しい。
- 初項と末項は1または2であり、隣接する2項間の差は −1, 0, 1 のいずれかである。
また、次の条件を満たす長さ テンプレート:Math の正整数列の数にも等しい。
- 初項と末項は1であり、隣接する2項間の差は −1, 0, 1 のいずれかである。
さらに、2次元デカルト座標平面において次の条件を満たす経路の数にも等しい。
- (0, 0) から出発し (テンプレート:Mvar, 0) まで到達する。
- 経路は、座標が両方とも非負整数である点（格子点）のみを結んだ折れ線になっている。
- ある格子点からその次の格子点へ向かう位置ベクトルは (0,1), (1,1), (1, −1) のいずれかである。
例えば、次の図は (0, 0) から (4, 0) へ到達する9通りのモツキン経路を示す。
数学の諸分科にわたって、モツキン数には少なくとも14通りの相異なる定義方法がある（このカウントはサーベイテンプレート:Harvtxt による）。テンプレート:Harvtxt は テンプレート:仮リンクの数がモツキン数を使って数えられることを示した。