اعداد کاتالان

اعداد کاتالان در ریاضیات ترکیبی، یک سری از اعداد طبیعی هستند که در مسائل شمارشی متنوع که معمولاً اشیا به صورت بازگشتی تعریف شده را در بر می‌گیرند، رخ می‌دهند. این اعداد به افتخار ریاضیدان بلژیکی شارل کاتالان (۱۸۹۴-۱۸۱۴) اعداد کاتالان نامیده می‌شوند. وی استنتاج مقدماتی از فرمول را کشف کرد. کاتالان مقالات متعددی در زمینه آنالیز، ترکیبیات، جبر، هندسه، احتمالات و نظریه اعداد منتشر کرد. درستی حدس او که اعداد ۰، ۱، ۸، ۹ تنها زوج اعداد توان کامل متوالی است که به صورت توانی می‌باشد در دهه ۱۹۷۰ ثابت شد.

تعریف

nاُمین عدد کاتالان عبارت است از:

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.

چند عدد اولیه کاتالان عبارتند از:

۱، ۲، ۵، ۱۴، ۴۲، ۱۳۲، ۴۲۹، ۱۴۳۰، ۴۸۶۲، ۱۶۷۹۶، ۵۸۷۸۶، ۲۰۸۰۱۲، ۷۴۲۹۰۰، ۲۶۷۴۴۴۰، ۹۶۹۴۸۴۵، ۳۵۳۵۷۶۷۰، ۱۲۹۶۴۴۷۹۰، ۴۷۷۶۳۸۷۰۰، ۱۷۶۷۲۶۳۱۹۰، ۶۵۶۴۱۲۰۴۲۰، ۲۴۴۶۶۲۶۷۰۲۰، ۹۱۴۸۲۵۶۳۶۴۰، ۳۴۳۰۵۹۶۱۳۶۵۰، ۱۲۸۹۹۰۴۱۴۷۳۲۴، ۴۸۶۱۹۴۶۴۰۱۴۵۲

خواص

یک عبارت دیگر برای $C_{n}$

به صورت زیر است:

C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1.

عبارت فوق نشان می‌دهد که $C_{n}$

یک عدد طبیعی است که این نتیجه از فرمول اول چندان بدیهی نبود. این عبارت اساس اثبات آندره در مورد صحت فرمول را تشکیل می‌دهد. هم چنین اعداد کاتالان از رابطه بازگشتی زیر نیز به دست می‌آیند:

C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.

و همچنین:

C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},

که می‌تواند برای محاسبه آن‌ها کاراتر باشد.

به‌طور مجانبی اعداد کاتالان به صورت $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

رشد می‌کنند که نشان می‌دهد که عبارت سمت راست برای ∞ →n به سمت یک میل می‌کند.(این عبارت می‌تواند با استفاده از تقریب استرلینگ برای !n اثبات شود) تنها اعدادی از دنباله کاتالان فرد هستند که به صورت

n={2^{k}}-1

هستند. بقیه همگی زوج می‌باشند.

کاربرد در ترکیبیات

تعداد زیادی از مسائل شمارشی در ترکیبیات هستند که راه حلی با استفاده از اعداد کاتالان برای آن‌ها ارائه شده‌است. کتاب ترکیبیات شمارشی جلد دوم اثر ریچارد استانلی شامل مجموعه‌ای از تمرین هاست که ۶۶ تفسیر مختلف از اعداد کاتالان را شرح می‌دهد. در زیر چند نمونه آمده‌است.

- $C_{n}$

تعداد کلمات Dyck به طول ۲n است. یک کلمه Dyck یک رشته است که n تاX و n تا Y دارد؛ به گونه‌ای که تعداد Yها در هر بخش آغازین آن بیشتر از تعداد Xهاست. برای مثال در زیر کلمات Dyck با طول ۶ آمده اند:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

- چنانچه هر نماد X را به صورت یک پرانتز باز ببینیم و هر نماد Y را یک پرانتز بسته آنگاه $C_{n}$

تعداد عباراتی که شامل n جفت پرانتزگذاری صحیح هستند را نشان می‌دهد.

((())) ()(()) ()()() (())() (()())

- $C_{n}$

تعداد راه‌های مختلفی است که n+۱ عامل می‌توانند پرانتزگذاری شوند. برای n=۳ به عنوان مثال ۵ پرانتزگذاری مختلف برای چهار عامل را داریم:

((ab)c)d\quad (a(bc))d\quad (ab)(cd)\quad a((bc)d)\quad a(b(cd))

- $C_{n}$

تعداد درخت‌های دودویی غیر هم ریخت با n راس است که بچه دارند که معمولاً رئوس داخلی یا شاخه گفته می‌شوند.

- $C_{n}$

تعداد راه‌های مختلفی است که یک چندضلعی محدب با n+۲ ضلع می‌تواند با وصل کردن رأس‌ها با خطوط مستقیم مثلث بندی شود. شش گوشه زیر برای n=۴ نشان می‌دهد:

اثبات فرمول

چندین راه برای نشان دادن اینکه چرا فرمول $C_{n}={\frac {1}{n+1}}{2n \choose n}$

مسائل ترکیبیاتی ذکر شده را حل می‌کند وجود دارد. اولین اثبات از تابع مولد استفاده می‌کند. دومین و سومین اثبات مثال‌هایی از اثبات نگاشت‌های دوطرفه هستند.

می بینیم که تعداد زیادی از مسائل ترکیبیاتی فوق از راه بازگشتی حل می‌شوند.

با استفاده از فرمول $C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0.$

می‌توانیم با استفاده از تکنیک‌های شناخته شده برای توابع مولد یک فرمول واضح برای اعداد کاتالان به دست بیاوریم. با تعریف

f(z)

که همه اعداد کاتالان را شامل می‌شود شروع می کنیم:

f(z)=C_{0}+C_{1}z+C_{2}z^{2}+C_{3}z^{3}+...=C_{n+1}=c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}

اگر (f(z را در خودش ضرب کنیم و $[f(z)]^{2}$

را به دست بیاوریم، نخستین جملات این چنین هستند:

...+ $[f(z)]^{2}=C_{0}C_{0}+(C_{1}C_{0}+C_{0}C_{1})z+(C_{2}C_{0}+C_{1}C_{1}+C_{0}C_{2})z^{2}$

ضرایب برای توان‌های z همانهایی هستند که از معادله $C_{n}={\frac {1}{n+1}}{2n \choose n}$

بر می‌آید

...+ $[f(z)]^{2}=C_{1}+C_{2}z+C_{3}z^{2}+C_{4}z^{3}$

اگر که (f(z رادر z ضرب کنیم و به آن $C_{0}$

را بیفزاییم به دست می آوریم:

$f(z)=C_{0}+z[f(z)]^{2}$

معادله فوق یک معادله درجه دو است که می‌توانیم ان را حل کنیم. آن را به صورت $zf^{2}-f-C_{0}=0$

می نویسیم. بنابراین به دست می آوریم:

$f(z)={\frac {1-{\sqrt {1-4x}}}{2x}}\quad (8)$

توجه کنید که ما علامت منفی را برگزیدیم. چون میدانیم که $f(0)=C_{0}=1$

؛ بنابراین اگر علامت مثبت را جایگذاری کنیم وقتی z→0، آنگاه

f(z)\to \infty

برای بسط از فرمول دوجمله‌ای استفاده می‌کنیم؛ اگر که با استفاده از فرمول دوجمله‌ای با نماهای اعشاری آشنا نیستید، نگران نباشید. دقیقاً همانگونه است؛ با این تفاوت که هیچگاه تمام نمی‌شود. بیایید به فرمول دوجمله‌ای برای یک نمای صحیح نگاهی بیندازیم و همان محاسبات را برای یک عدد اعشاری انجام دهیم. اگر n یک عدد صحیح باشد، فرمول دوجمله‌ای به این قرار است:

... $(a+b)^{n}=a^{n}+{\frac {n}{1}}a^{n-1}b^{1}+{\frac {n(n-1)}{2.1}}a^{n-2}b^{2}+{\frac {n(n-1)(n-2)}{3.2.1}}a^{n-3}b^{3}+$

اگرn یک عدد صحیح باشد، صورت کسر سرانجام یک عبارت به صورت (n-n)خواهد داشت؛ بنابراین آن جمله و تمام جملات بعد ازآن صفر خواهند بود. اگر nعدد صحیح نباشد و مثلاً برای مثال ما ${\frac {1}{2}}$

باشد، صورت کسر صفر را خواهد گذراند و ادامه خواهد یافت. در زیر تعدادی از نخستین جملات بسط آمده اند:

$(1-4x)^{({\frac {1}{2}})}=1-{\frac {({\frac {1}{2}})}{1}}4z+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})}{2.1}}(4z)^{2}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})}{3.2.1}}(4z)^{3}+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})}{4.3.2.1}}(4z)^{4}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})(-{\frac {7}{2}})}{5.4.3.2.1}}(4z)^{5}+...$

و به دست می آوریم:

$(1-4x)^{\frac {1}{2}}=1-{\frac {1}{1!}}2z-{\frac {1}{2!}}4z^{2}-{\frac {3.1}{3!}}8z^{3}-{\frac {5.3.1}{4!}}16z^{4}-{\frac {7.5.3.1}{5!}}32z^{5}-...\quad (9)$

از معادله 8 و 9 داریم:

$f(z)=1+{\frac {1}{2!}}2z+{\frac {3.1}{3!}}4z^{2}+{\frac {5.3.1}{4!}}8z^{3}+{\frac {7.5.3.1}{5!}}16z^{4}+...\quad (10)$

عباراتی نظیر 7.5.3.1 کمی دردسرسازند. این عبارات شبیه فاکتوریل‌ها هستند؛ اما اعداد زوج را در برندارند. اما توجه کنید که $2^{2}.2!=4.2$

و

2^{3}.3!=6.4.2

و

2^{4}.4!=8.6.4.2

و مشابه این. بنابراین

(7.5.3.1).2^{4}4!=8!

. بنابراین اگر این ایده را برای معادله 10 به کار ببریم به دست می آوریم:

$f(z)=1+{\frac {1}{2}}{\frac {2!}{1!1!}}z+{\frac {1}{3}}{\frac {4!}{2!2!}}z^{2}+{\frac {1}{4}}{\frac {6!}{3!3!}}z^{3}+{\frac {1}{5}}{\frac {8!}{4!4!}}z^{4}+...=\sum _{i=0}^{\infty }{\frac {1}{i+1}}{2i \choose i}z^{i}$

از این عبارت می‌توانیم نتیجه بگیریم که n امین عدد کاتالان با این فرمول به دست می‌آید:

$C_{i}={\frac {1}{i+1}}{2i \choose i}$

ماتریس هانکل

ماتریس n_*n هانکل که هر درایه $(i,j)$

آن عدد کاتالان

C_{i+j-2}

است بدون توجه به n دترمینانی برابر یک دارد. برای مثال برای n=۴ داریم:

توجه کنید که درایه‌ها شیفت خورده‌اند و به صورت $C_{i+j-1}$

بازهم بدون توجه به n دترمینان یک است. برای مثال برای n=۴ داریم:

تاریخچه

دنباله کاتالان نخستین بار در قرن هیجدهم توسط لئونارد اویلر به کار برده شد که به تعداد راه‌های تقسیم کردن یک چندضلعی به مثلث علاقه‌مند بود. شارل کاتالان ارتباط بین پرانتزگذاری عبارات را در طول کشفیاتش در باره معمای برج‌های هانوی کشف کرد. ترفند شمارشی برای کلمات Dyck نیز توسط د.آندره در سال ۱۸۸۷ به دست آمد.

پیوندهای مفید

بررسی روش‌های برنامه‌نویسی اعداد کاتالان

منابع

ویکی‌پدیای انگلیسی

اعداد کاتالان