モツキン数のソースを表示

[[数学]]において[[自然数]] {{mvar|n}} に対する'''モツキン数'''（モツキンすう、{{Lang-en-short|Motzkin number}}）とは、[[円周]]上の相異なる {{mvar|n}} 個の点を互いに交わらないような[[線分]]で結ぶ方法の数である。点は互いに区別がつき、また結ばれていない点があってもよい。名称は{{仮リンク|テオドール・モツキン|en|Theodore Motzkin|de|Theodore Motzkin}}にちなむ。モツキン数は[[幾何学]]、[[組合せ数学]]、[[数論]]といった分野に多様な応用がある。

<math>n = 0, 1, \dots</math> に対するモツキン数 <math>M_n</math> は以下のとおりである。

: 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|id=A001006}}）

== 例 ==

次の図は、円周上の 4 個の点を互いに交わらないように結ぶ 9 通りの[[弦 (数学)|弦]]の引き方を示す（{{math|1=''M''<sub>4</sub> = 9}}）。

:[[Image:MotzkinChords4.svg]]

次の図は、円周上の 5 個の点を互いに交わらないように結ぶ 21 通りの弦の引き方を示す（{{math|1=''M''<sub>5</sub> = 21}}）。

:[[Image:MotzkinChords5.svg]]

== 性質 ==

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

:<math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}</math>

モツキン数は[[二項係数]]と[[カタラン数]]を使って書くことができる（ <math>\lfloor x\rfloor</math> は[[床関数]]）。

:<math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} C_k</math>

'''モツキン素数'''（Motzkin prime）は[[素数]]であるようなモツキン数である。{{Asof|2013|October}}、4個のモツキン素数が見つかっている。

: 2, 127, 15511, 953467954114363 （{{OEIS|id=A092832}}）

== 組合せ数学的な解釈 ==

{{mvar|n}} に対するモツキン数は、次の条件を満たす長さ {{math|1=''n'' &minus; 1}} の[[数列|正整数列]]の数に等しい。
* 初項と末項は1または2であり、隣接する2項間の差は &minus;1, 0, 1 のいずれかである。

また、次の条件を満たす長さ {{math|1=''n'' + 1}} の正整数列の数にも等しい。
* 初項と末項は1であり、隣接する2項間の差は &minus;1, 0, 1 のいずれかである。

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

:[[Image:Motzkin4.svg]]

数学の諸分科にわたって、モツキン数には少なくとも14通りの相異なる定義方法がある（このカウントはサーベイ{{harvtxt|Donaghey|Shapiro|1977}} による）。{{harvtxt|Guibert|Pergola|Pinzani|2001}} は {{仮リンク|vexillary involution|en|vexillary involution}}の数がモツキン数を使って数えられることを示した。

==関連項目==
* {{仮リンク|ドラノワ数|en|Delannoy number}}
* {{仮リンク|ナラヤナ数|en|Narayana number}}
* {{仮リンク|シュレーダー数|en|Schröder number}}

==参考文献==
* {{citation
 | last = Bernhart
 | first = Frank R.
 | title = Catalan, Motzkin, and Riordan numbers 
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 204
 | year = 1999
 | pages = 73–112
 | doi = 10.1016/S0012-365X(99)00054-0
 | issue = 1-3}}
* {{citation
 | last1 = Donaghey
 | first1 = R.
 | last2 = Shapiro
 | first2 = L. W.
 | title = Motzkin numbers
 | journal = [[Journal of Combinatorial Theory]] | series = Series A
 | volume = 23
 | issue = 3
 | year = 1977
 | pages = 291–301
 | mr = 0505544
 | doi = 10.1016/0097-3165(77)90020-6}}
* {{Citation | last1=Guibert | first1=O. | last2=Pergola | first2=E. | last3=Pinzani | first3=R. | title=Vexillary involutions are enumerated by Motzkin numbers | doi=10.1007/PL00001297 | year=2001 | journal=Annals of Combinatorics | issn=0218-0006 | volume=5 | issue=2 | pages=153–174 | mr=1904383}}
* {{citation
 | last = Motzkin
 | first = T. S. | authorlink = Theodore Motzkin
 | title = Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
 | journal = [[Bulletin of the American Mathematical Society]]
 | volume = 54
 | year = 1948
 | pages = 352–360
 | doi = 10.1090/S0002-9904-1948-09002-4
 | issue = 4}}

==外部リンク==
* {{MathWorld|title=Motzkin Number|urlname=MotzkinNumber}}

{{素数の分類}}
{{DEFAULTSORT:もつきんすう}}
[[Category:数論]]
[[Category:素数]]
[[Category:組合せ論]]
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]