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

n = 0 , 1 , … {\displaystyle n=0,1,\dots } に対するモツキン数 M n {\displaystyle M_{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）。
性質

モツキン数は次の漸化式を満たす。 M n = M n − 1 + ∑ i = 0 n − 2 M i M n − 2 − i = 2 n + 1 n + 2 M n − 1 + 3 n − 3 n + 2 M n − 2 {\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}}

モツキン数は二項係数とカタラン数を使って書くことができる（ ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数）。 M n = ∑ k = 0 ⌊ n / 2 ⌋ ( n 2 k ) C k {\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k}}

モツキン素数（Motzkin prime）は素数であるようなモツキン数である。2013年 (2013-October)現在[update]、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, MR.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}0505544 

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 

外部リンク

Weisstein, Eric W. "Motzkin Number". mathworld.wolfram.com (英語).

表

話

編

歴
素数の分類
生成式

フェルマー (22n + 1)

メルセンヌ (2p − 1)

二重メルセンヌ (22p−1 − 1)

ワグスタッフ ((2p + 1)/3)

プロス (k・2n + 1)

階乗 (n! ± 1)

素数階乗 (pn# ± 1)

ユークリッド (pn# + 1)

ピタゴラス (4n + 1)

ピアポント (2u・3v + 1)

Quartan（英語版） (x4 + y4)

ソリナス（英語版） (2a ± 2b ± 1)

カレン (n・2n + 1)

ウッダル (n・2n − 1)

Cuban（英語版） ((x3 − y3)/(x − y))

キャロル ((2n − 1)2 − 2)

Kynea ((2n + 1)2 − 2)

レイランド (xy + yx)

サービト（英語版） (3・2n − 1)

ミルズ ([A]3n)

漸化式（英語版）

フィボナッチ

リュカ

ペル

ニューマン?シャンクス?ウィリアムズ

ペラン

分割

ベル

モツキン

各種の性質

ヴィーフェリッヒ（英語版） (対（英語版）)

ウォール?孫?孫（英語版）

ウォルステンホルム

ウィルソン

幸運

フォーチュン