モツキン数

数学において、n次モツキン数は、円上のn点 間に交差しない弦を引くさまざまな方法の数です (すべての点に弦が接している必要はありません)。モツキン数はセオドア・モツキンにちなんで名付けられ、幾何学、組合せ論、数論で多様に応用されています。

のモツキン数は次の数列を形成します 。${\displaystyle M_{n}}$${\displaystyle n=0,1,\dots }$

1、1、2、4、9、21、51、127、323、835 、...（OEISのシーケンスA001006）​​​​​​​​​​

次の図は、円上の 4 点間に交差しない弦を描く 9 つの方法を示しています ( M ₄ = 9 )。

次の図は、円上の 5 点間に交差しない弦を描く 21 通りの方法を示しています ( M ₅ = 21 )。

モツキン数は再帰関係を満たす

${\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}.}$

モツキン数は二項係数とカタラン数で表すことができます。

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k},}$

そして逆に、^[1]

${\displaystyle C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}}$

これにより

${\displaystyle \sum _{k=0}^{n}C_{k}=1+\sum _{k=1}^{n}{\binom {n}{k}}M_{k-1} 。}$

モツキン数の 生成関数は 次式を満たす。${\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}}$

${\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}$

そして、明示的に次のように表現される。

${\displaystyle m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.}$

モツキン数の積分表現は次のように与えられる。

${\displaystyle M_{n}={\frac {2}{\pi }}\int _{0}^{\pi }\sin(x)^{2}(2\cos(x)+1)^{n}dx}$。

漸近的な挙動を示す

${\displaystyle M_{n}\sim {\frac {1}{2{\sqrt {\pi }}}}\left({\frac {3}{n}}\right)^{3/2}3^{n},~n\to \infty }$。

モツキン素数は、素数であるモツキン数です。このような素数は 4 つ知られています。

2, 127, 15511, 953467954114363 ( OEISの配列A092832 )

nのモツキン数は、開始要素と終了要素が 1 または 2 で、連続する任意の 2 つの要素の差が -1、0、または 1である長さn − 1の正の整数列の数でもあります。同様に、 nのモツキン数は、開始要素と終了要素が 1 で、連続する任意の 2 つの要素の差が -1、0、または 1 である 長さn + 1の正の整数列の数です。

また、 nに対するモツキン数は、各ステップで右方向（上、下、またはまっすぐ）への移動のみが許可され、 y = 0 軸より下への移動は禁止されている場合に、 nステップで座標 (0, 0) から座標 ( n、0)までのグリッドの右上象限上の経路の数を示します。

たとえば、次の図は (0, 0) から (4, 0) までの 9 つの有効な Motzkin パスを示しています。

ドナギーとシャピロ (1977) がモツキン数の調査で列挙したように、数学のさまざまな分野で少なくとも 14 種類のモツキン数の表現があります。ギベール、ペルゴラ、ピンザニ (2001) は、ベキシラ反転がモツキン数で列挙されることを示しました。

• 交差が許される場合のコード描画方法の数を表す電話番号
• デラノワ数
• ナラヤナ番号
• シュレーダー数

• ベルンハート、フランク R. (1999)、「カタラン数、モツキン数、リオルダン数」、離散数学、204 (1–3): 73–112、doi : 10.1016/S0012-365X(99)00054-0
• Donaghey, R.; Shapiro, LW (1977)、「Motzkin 数」、Journal of Combinatorial Theory、シリーズ A、23 (3): 291–301、doi : 10.1016/0097-3165(77)90020-6、MR  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、MR  1904383、S2CID  123053532
• モツキン、TS (1948)、「超曲面のクロス比の関係、および多角形の分割、永久優勢、非結合積の組み合わせ式」、アメリカ数学会誌、54 (4): 352–360、doi : 10.1090/S0002-9904-1948-09002-4

• Weisstein、Eric W.「Motzkin 数」。MathWorld。