در ترکیبیات، اعداد کاتالان که عموما آنرا با Cn نمایش میدهند، دنبالهای است از اعداد طبیعی که به نام ریاضیدان بلژیکی، اوژن کاتالان نامگذاری شده است.
دنبالهی کاتالان برای اندیسهای حسابی (0,1,2,...) تعریف میشود که فرمول بازگشتی آن به صورت زیر است: Cn={1if n=0;n∑i=0CiCn−i−1if n>1.
عناصر اولیهی این دنباله عبارتند از: 1,1,2,5,14,42,132,429,1430,4862,...
عنصر n ام دنباله کاتالان برابر است با تعداد پرانتزگذاریهای معتبر به طول 2n. یک پرانتزگذاری رشتهای است متشکل از ) و (.
یک پرانتزگذاری s معتبر است اگر و تنها اگر یکی از خواص زیر را دارا باشد:
تعریف پرانتزگذاری نیز همانند تعریف دنبالهی کاتالان بازگشتیاست.
فرض کنیم تعداد پرانتزگذاریهای معتبر به طول 2n برابر باشد با pn. میدانیم p0=1. برای :n>0
میتوانیم شروط دوم و سوم را ادغام کنیم به یک شرط: پرانتزگذاریهای معتبر a و b وجود داشته باشند که: s=(a)b.
بنابراین مجموع طول a و b باید برابر 2n−2 باشد. پس تعداد حالات مختلف انتخاب a و b برابراست با مجموع pi×pn−i−1 برای همهی i های بزرگترمساوی 0 و کوچکترمساوری n−1. یعنی: pn=n−1∑i=0pipn−i−1
که این همان تعریف دنبالهی کاتالان است.
C_n = \frac{1}{n+1} \binom{2n}{n}
این فرمول را اثبات کنید.
پاسخ
تعریف: یک پرانتزگذاری میزان است اگر و تنها اگر تعداد پرانتزهای باز آن برابر باشد با تعداد پرانتزهای بستهاش. اگر B_n برابر با تعداد پرانتزگذاریهای میزان به طول 2n باشد، میتوان نشان داد B_n = \binom{2n}{n}.
الگوریتم ۱: با داشتن یک پرانتزگذاری s: شمارندهای با نام ctr تعریف میکنیم و ابتدا آنرا برابر صفر قرار میدهیم. از اولین پرانتز s شروع کرده، همهی حروفرا میبینیم و هرگاه به پرانتز بازی رسیدیم شمارنده را یکی افزایش و هرگاه به پرانتز بستهای رسیدیم آنرا یکی کاهش میدهیم. s معتبر است اگر و تنها اگر شمارنده هیچگاه منفی نشود و درانتها برابر صفر شود. s میزان است اگر و تنها اگر شمارنده در انتها صفر شود.
لم: یک پرانتزگذاری s میزان است اگر و تنها اگر یکی از شروط زیر برقرار باشد:
اثبات: اگر s با پرانتز باز شروع شده باشد: اگر پرانتز بعدی اش بسته باشد، x تهیاست و شرط اول برقرار است. در غیر این صورت: الگوریتم ۱ را روی پرانتزهای دوم به بعد s اجرا میکنیم و شمارنده در اندیس i > 2 از s منفی میشود. زیرا با حذف پرانتز اول s تعداد پرانتزهای بستهاش بیشتر میشود و پرانتز دوم s باز است. اگر رشتهی حاصل از چسبانیدن پرانتزهای دوم تا j-1 ام از s را v بنامیم، میدانیم v تهی نیست (چون j > 2). و چون دراندیس j ام اولین جایی است که شمارنده منفی شده است، اگر الگوریتم ۱ را روی v اجرا کنیم شمارنده منفی نمیشود و درانتها صفر است. پس v معتبر است و x=v و شرط اول برقرار است.
اگر s با پرانتز بسته شروع شده باشد: اگر پرانتز بعدی اش باز باشد، x تهیاست و شرط دوم برقرار است. در غیر این صورت: الگوریتم ۱ را روی پرانتزهای دوم به بعد s اجرا میکنیم و شمارنده در اندیس i > 2 از s مثبت میشود. زیرا با حذف پرانتز اول s تعداد پرانتزهای بازش بیشتر میشود و پرانتز دوم s بسته است. اگر رشتهی حاصل از چسبانیدن پرانتزهای دوم تا j-1 ام از s را v بنامیم، میدانیم v تهی نیست (چون j > 2). و چون دراندیس j ام اولین جایی است که شمارنده مثبت شده است، اگر الگوریتم ۱ را روی v اجرا کنیم شمارنده مثبت نمیشود و درانتها صفر است. پس v^{-1} معتبر است و x=v و شرط دوم برقرار است.
بنابراین: B_n = 2\sum \limits_{i=0}^{n-1} B_n C_{n-i-1}
همچنین، هر پرانتزگذاری نامعتبر میزان با s) شروع میشود که در آن s معتبر است. زیرا با اجرای الگوریتم ۱، دراندیسی شمارنده منفی میشود. پس:
B_n - C_n = \sum \limits_{i=0}^{n-1} \binom{2i + 1}{i} C_{n-1-i} = \sum \limits_{i=0}^{n-1} \frac{2i + 1}{i + 1}B_i C_{n-i-1}
اگر فرض کنیم B_n = d_n C_n (که d_n = \frac{B_n}{C_n}) و دو عبارت بالا را از هم کم کنیم، داریم: C_n = 2\sum \limits_{i=0}^{n-1} d_i C_i C_{n-i-1} - \sum \limits_{i=0}^{n-1} \frac{2i + 1}{i + 1}d_i C_i C_{n-i-1} = \sum \limits_{i=0}^{n-1} \frac{d_i}{i + 1}d_i C_i C_{n-i-1}
پس: \sum \limits_{i=0}^{n-1} \frac{d_i}{i + 1}d_i C_i C_{n-i-1} = \sum \limits_{i=0}^{n} C_i C_{n-i-1}
پس d_i = i + 1، بنابراین:
B_n = (n + 1) C_n \longrightarrow C_n = \frac{1}{n+1} B_n = \frac{1}{n+1} \binom{2n}{n}
تعداد راه های مثلثبندی یک 11ضلعی محدب را بیابید.
پاسخ
اگر تعداد راههای مثلثبندی یک nضلعی محدب t_n باشد:
t_n = t_{n-1} + \sum \limits_{i=3}^{n-1} t_i t_{n-i+1}
فرض کنیم s_n = t_{n+2} و s_0 = 1 بنابر این: s_n = s_0 s_{n-1} + \sum \limits_{i=1}^{n-1} s_i s_{n-i-1} = \sum \limits_{i=0}^{n-1} s_i s_{n-i-1}
پس: s_n = C_n. بنابراین: t_{11} = s_9 = C_9 = 4862.