モツキン数
数学において自然数 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)
モツキン数は次の漸化式を満たす。
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)現在、4個のモツキン素数が見つかっている。
2, 127, 15511, 953467954114363 (オンライン整数列大辞典の数列 A092832)