Processing math: 28%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

در ترکیبیات، اعداد کاتالان که عموما آن‌را با Cn نمایش می‌دهند، دنباله‌ای است از اعداد طبیعی که به نام ریاضی‌دان بلژیکی، اوژن کاتالان نام‌گذاری شده است.

تعریف ریاضی

دنباله‌ی کاتالان برای اندیس‌های حسابی (0,1,2,...) تعریف می‌شود که فرمول‌ بازگشتی‌ آن به صورت زیر است: Cn={1if n=0;ni=0CiCni1if n>1.

عناصر اولیه‌ی این دنباله عبارتند از: 1,1,2,5,14,42,132,429,1430,4862,...

تعریف شمارشی

عنصر n ام دنباله کاتالان برابر است با تعداد پرانتزگذاری‌های معتبر به طول 2n. یک پرانتزگذاری رشته‌ای است متشکل از ) و (.

یک پرانتزگذاری s معتبر است اگر و تنها اگر یکی از خواص زیر را دارا باشد:

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

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

اثبات

فرض کنیم تعداد پرانتزگذاری‌های معتبر به طول 2n برابر باشد با pn. می‌دانیم p0=1. برای :n>0

می‌توانیم شروط دوم و سوم را ادغام کنیم به یک شرط: پرانتزگذاری‌‌های معتبر a و b وجود داشته باشند که: s=(a)b.

بنابراین مجموع طول a و b باید برابر 2n2 باشد. پس تعداد حالات مختلف انتخاب a و b برابراست با مجموع pi×pni1 برای همه‌ی i های بزرگ‌ترمساوی 0 و کوچک‌ترمساوری n1. یعنی: pn=n1i=0pipni1

که این همان تعریف دنباله‌ی کاتالان است.

صورت صریح

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.


ابزار صفحه