عدد موتزکین

عدد موتزکین n ام، در ریاضیات عبارت است از تعداد روش‌های مختلف رسم وترهای غیر متقاطع بین n نقطه روی یک دایره به صورتی که هر نقطه الزاماً با یک وتر تماس ندارد). اعداد موتزکین به نام تئودور موتزکین نامگذاری شده‌اند و کاربردهای متنوعی در هندسه، ترکیبات و نظریه اعداد دارند.

اعداد موتزکین $M_{n}$ برای $n=0,1,\dots$ دنباله زیر را تشکیل می‌دهد:

۱، ۱، ۲، ۴، ۹، ۲۱، ۵۱، ۱۲۷، ۳۲۳، ۸۳۵، … (دنباله A001006 در OEIS)

مثال‌ها

شکل زیر ۹ روش برای رسم وترهای غیر متقاطع بین ۴ نقطه روی یک دایره را نشان می‌دهد (M₄ = ۹):

شکل زیر ۲۱ روش برای رسم وترهای غیر متقاطع بین ۵ نقطه روی یک دایره را نشان می‌دهد (M₅ = ۲۱):

خواص

اعداد موتزکین روابط بازگشتی را برآورده می‌کند:

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

اعداد موتزکین را می‌توان بر حسب ضرایب دوجمله ای و اعداد کاتالان نیز بیان کرد:

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

و برعکس،

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

که نتیجه آن به صورت زیر خواهد بود:

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

تابع مولد $m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}$ از اعداد موتزکین نتیجه زیر را برآورد می‌کند:

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

و به صورت زیر بیان می‌شود:

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

یک نمایش انتگرالی از اعداد موتزکین به صورت زیر است:

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

آنها رفتار مجانبی نیز دارند:

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

عدد اول موتزکین یک عدد موتزکین است که جزء اول است. از سال ۲۰۱۹، فقط چهار عدد اول از این قبیل شناخته شده‌است:

2, 127, 15511, 953467954114363 (دنباله A092832 در OEIS)

تفاسیر ترکیبی

عدد موتزکین برای n نیز تعداد دنباله‌های اعداد صحیح مثبت به طول n − ۱ است که در آن عناصر آغازین و انتهایی ۱ یا ۲ هستند و تفاوت بین هر دو عنصر متوالی −1، ۰ یا ۱ است.

به‌طور مشابه، عدد موتزکین برای n هم تعداد دنباله‌های اعداد صحیح مثبت به طول n + 1 است که در آن عناصر آغازین و انتهایی ۱ هستند و تفاوت بین هر دو عنصر متوالی −1، ۰ یا ۱ است.

همچنین، عدد موتزکین برای n بیانگر تعداد مسیرها در ربع سمت راست بالای یک شبکه از مختصات (۰، ۰) تا مختصات (n، ۰) در n مرحله است به صورتی که فقط مجاز باشد به سمت راست حرکت کرد (بالا، پایین یا مستقیم) ولی در هر مرحله فرو افتادن به زیر محور y = ۰ ممنوع است.

به عنوان مثال، شکل زیر ۹ مسیر معتبر موتزکین را از (۰، ۰) تا (۴، ۰) نشان می‌دهد:

حداقل چهارده نمود مختلف از اعداد موتزکین در شاخه‌های مختلف ریاضیات وجود دارد، به شکلی که (Donaghey و Shapiro 1977) در بررسی اعداد موتزکین برشمرده اند. (Guibert، Pergola و Pinzani 2001) نشان دادند که چرخه‌های وکسیلاری با اعداد موتزکین شمارش می‌شوند.

منابع

• 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 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
• 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.