المپدیا

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

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:اعداد کاتالان

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

در ترکیبیات، اعداد کاتالان که عموما آن‌را با $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$ معتبر است اگر و تنها اگر یکی از خواص زیر را دارا باشد:

  1. تهی باشد
  2. پرانتزگذاری معتبری مانند $t$ وجود داشته باشد که: $s = (t)$
  3. پرانتزگذاری‌های معتبر ناتهی $x$ و $y$ وجود داشته باشند که: $s = xy$

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

اثبات

فرض کنیم تعداد پرانتزگذاری‌های معتبر به طول $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$ میزان‌ است اگر و تنها اگر یکی از شروط زیر برقرار باشد:

  1. پرانتزگذاری معتبر $x$ و پرانتزگذاری میزان $y$ وجود داشته باشند که: $s=(x)y$
  2. پرانتزگذاری معتبر $x$ و پرانتزگذاری میزان $y$ وجود داشته باشند که: $s=)x^{-1}(y$ که $t^{-1}$ حاصل برعکس کردن پرانتزهای $t$ است

اثبات: اگر $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$ باشد:

  1. $t_3 = 1$
  2. راس $n$ ام را درنظر بگیرید. اگر وتری از این راس رسم شود: اگر یک وتر ترسیم کنیم که $i$ راس یک طرف و $n-i+2$ راس طرف دیگر آن باشد، تعداد راه های مثلث‌بندی یک طرف $t_i$ و تعداد راه‌‌های مثلث بندی طرف دیگر $t{n-i+1}$ است. اگر وتری رسم نشود پس وتری بین دو راس مجاورش وجود دارد، و مثلث‌بندی باقی چند ضلعی $t_{n-1}$ راه دارد. پس:

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


ابزار صفحه