در ترکیبیات، اعداد کاتالان که عموما آنرا با $C_n$ نمایش میدهند، دنبالهای است از اعداد طبیعی که به نام ریاضیدان بلژیکی، اوژن کاتالان نامگذاری شده است.
دنبالهی کاتالان برای اندیسهای حسابی ($0, 1, 2, ...$) تعریف میشود که فرمول بازگشتی آن به صورت زیر است: $$ C_n = \begin{cases} 1 & \mbox{if } n = 0; \\ \sum \limits_{i=0}^{n} C_i C_{n-i-1} & \mbox{if } n > 1. \\ \end{cases} $$
عناصر اولیهی این دنباله عبارتند از: $$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...$$
عنصر $n$ ام دنباله کاتالان برابر است با تعداد پرانتزگذاریهای معتبر به طول $2n$. یک پرانتزگذاری رشتهای است متشکل از $)$ و $($.
یک پرانتزگذاری $s$ معتبر است اگر و تنها اگر یکی از خواص زیر را دارا باشد:
تعریف پرانتزگذاری نیز همانند تعریف دنبالهی کاتالان بازگشتیاست.
فرض کنیم تعداد پرانتزگذاریهای معتبر به طول $2n$ برابر باشد با $p_n$. میدانیم $p_0 = 1$. برای $:n > 0$
میتوانیم شروط دوم و سوم را ادغام کنیم به یک شرط: پرانتزگذاریهای معتبر $a$ و $b$ وجود داشته باشند که: $s = (a)b$.
بنابراین مجموع طول $a$ و $b$ باید برابر $2n-2$ باشد. پس تعداد حالات مختلف انتخاب $a$ و $b$ برابراست با مجموع $p_{i} \times p_{n-i-1}$ برای همهی $i$ های بزرگترمساوی $0$ و کوچکترمساوری $n-1$. یعنی: $p_n = \sum \limits_{i=0}^{n-1} p_i p_{n-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$.