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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

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

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

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

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

خواص[ویرایش]

یک عبارت دیگر برای C_n به صورت زیر است:

C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 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\ge 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=۴ نشان می‌دهد:

Catalan-Hexagons-example.svg

اثبات فرمول[ویرایش]

چندین راه برای نشان دادن اینکه چرا فرمول 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\ge 0. می توانیم با استفاده از تکنیک‌های شناخته شده برای توابع مولد یک فرمول واضح برای اعداد کاتالان به دست بیاوریم. با تعریف f(z) که همه اعداد کاتالان را شامل می‌شود شروع می کنیم: f(z)=C_0+C_1z+C_2z^2+C_3z^3+...= C_{n+1}=c(x)=\sum_{n=0}^\infty C_n x^n

اگر (f(z را در خودش ضرب کنیم و [f(z)]^2 را به دست بیاوریم، نخستین جملات این چنین هستند:

...+[f(z)]^2 = C_0C_0 + (C_1C_0 + C_0C_1)z + (C_2C_0 + C_1C_1 + C_0C_2)z^2

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

...+[f(z)]^2 = C_1 + C_2z + C_3z^2 + C_4z^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=۴ داریم: 829c64a1026582f04e6e123d1bb9a288.png

توجه کنید که درایه‌ها شیفت خورده اند و به صورت C_{i+j-1} بازهم بدون توجه به n دترمینان یک است. برای مثال برای n=۴ داریم:

D26d37a2ef70ea301f27a76ea9febb9e.png

تاریخچه[ویرایش]

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

پیوندهای مفید[ویرایش]

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

منابع[ویرایش]

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

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