پرش به محتویات

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

اعداد کاتالان یک دنباله‌ی عددی هستند که در تعدادی از مسائل ترکیبیاتی، به‌ویژه آن‌هایی که شامل اشیاء تعریف‌شده به صورت بازگشتی هستند، کاربرد دارند.

این دنباله به نام ریاضی‌دان بلژیکی، کاتالان که در قرن نوزدهم می‌زیست، نام‌گذاری شده است. (در واقع، این دنباله پیش از او برای اویلر، که یک قرن قبل از کاتالان زندگی می‌کرد، شناخته شده بود).

چند عدد کاتالان اول $C_n$ (با شروع از صفر) عبارتند از:

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

کاربرد در برخی مسائل ترکیبیاتی

عدد کاتالان $C_n$ پاسخ مسائل زیر است:

  • تعداد دنباله‌های پرانتزبندی صحیح متشکل از $n$ پرانتز باز و $n$ پرانتز بسته.
  • تعداد درختان دودویی کاملِ ریشه‌دار با $n + 1$ برگ (رأس‌ها شماره‌گذاری نشده‌اند). یک درخت دودویی ریشه‌دار کامل است اگر هر رأس یا دو فرزند داشته باشد یا هیچ فرزندی نداشته باشد.
  • تعداد روش‌های پرانتزبندی کامل $n + 1$ عامل.
  • تعداد مثلث‌بندی‌های یک چندضلعی محدب با $n + 2$ ضلع (یعنی تعداد راه‌های افراز چندضلعی به مثلث‌های مجزا با استفاده از قطرها).
  • تعداد روش‌های اتصال $2n$ نقطه روی یک دایره برای تشکیل $n$ وتر غیرمتقاطع.
  • تعداد درختان دودویی کامل غیر یکریخت با $n$ گره داخلی (یعنی گره‌هایی که حداقل یک فرزند دارند).
  • تعداد مسیرهای شبکه‌ای یکنوا از نقطه $(0, 0)$ به نقطه $(n, n)$ در یک شبکه مربعی به اندازه $n \times n$، که از بالای قطر اصلی (قطری که $(0, 0)$ را به $(n, n)$ وصل می‌کند) عبور نمی‌کنند.
  • تعداد جایگشت‌های به طول $n$ که می‌توانند با پشته مرتب‌سازی شوند (یعنی می‌توان نشان داد که یک بازآرایی با پشته مرتب‌شدنی است اگر و تنها اگر هیچ اندیس $i < j < k$ وجود نداشته باشد که $a_k < a_i < a_j$).
  • تعداد افرازهای غیرمتقاطع یک مجموعه از $n$ عنصر.
  • تعداد روش‌های پوشاندن نردبان $1 \ldots n$ با استفاده از $n$ مستطیل (نردبان از $n$ ستون تشکیل شده است، که ستون $i$-ام ارتفاع $i$ دارد).

محاسبات

دو فرمول برای اعداد کاتالان وجود دارد: بازگشتی و تحلیلی. از آنجا که معتقدیم تمام مسائل ذکر شده در بالا معادل هستند (پاسخ یکسانی دارند)، برای اثبات فرمول‌های زیر، مسئله‌ای را انتخاب می‌کنیم که اثبات با آن ساده‌تر است.

فرمول بازگشتی

$$C_0 = C_1 = 1$$
$$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$$

فرمول بازگشتی را می‌توان به راحتی از مسئله دنباله پرانتزبندی صحیح استنتاج کرد.

چپ‌ترین پرانتز باز $l$ به یک پرانتز بسته مشخص $r$ متناظر است، که دنباله را به دو بخش تقسیم می‌کند که هر کدام به نوبه خود باید یک دنباله پرانتزبندی صحیح باشند. بنابراین فرمول نیز به دو بخش تقسیم می‌شود. اگر $k = {r - l - 1}$ را تعریف کنیم، آنگاه برای یک $r$ ثابت، دقیقاً $C_k C_{n-1-k}$ دنباله پرانتزی وجود خواهد داشت. با جمع زدن این مقدار روی تمام $k$های مجاز، به رابطه بازگشتی برای $C_n$ می‌رسیم.

همچنین می‌توانید به این شکل فکر کنید. طبق تعریف، $C_n$ تعداد دنباله‌های پرانتزبندی صحیح را نشان می‌دهد. حال، دنباله ممکن است به دو بخش به طول $k$ و ${n - k}$ تقسیم شود، که هر کدام باید یک دنباله پرانتزبندی صحیح باشند. مثال:

$( ) ( ( ) )$ می‌تواند به دو بخش $( )$ و $( ( ) )$ تقسیم شود، اما نمی‌تواند به $( ) ($ و $( ) )$ تقسیم شود. دوباره با جمع زدن روی تمام $k$‌های مجاز، به رابطه بازگشتی برای $C_n$ می‌رسیم.

پیاده‌سازی با C++

const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

فرمول تحلیلی

$$C_n = \frac{1}{n + 1} {\binom{2n}{n}}$$

(در اینجا $\binom{n}{k}$ ضریب دوجمله‌ای معمول را نشان می‌دهد، یعنی تعداد راه‌های انتخاب $k$ شیء از مجموعه‌ی $n$ شیء).

فرمول بالا را می‌توان به راحتی از مسئله مسیرهای یکنوا در شبکه مربعی نتیجه گرفت. تعداد کل مسیرهای یکنوا در یک شبکه به اندازه $n \times n$ برابر با $\binom{2n}{n}$ است.

حال تعداد مسیرهای یکنوایی که از قطر اصلی عبور می‌کنند را می‌شماریم. چنین مسیرهایی را که از قطر اصلی عبور می‌کنند در نظر بگیرید و اولین یالی را که بالای قطر اصلی قرار دارد پیدا کنید. کل مسیر را بعد از این یال، نسبت به قطر اصلی بازتاب دهید. نتیجه همیشه یک مسیر یکنوا در شبکه $(n - 1) \times (n + 1)$ خواهد بود. از طرف دیگر، هر مسیر یکنوا در شبکه $(n - 1) \times (n + 1)$ باید قطر را قطع کند. از این رو، ما تمام مسیرهای یکنوایی را که از قطر اصلی در شبکه $n \times n$ عبور می‌کنند، شمارش کرده‌ایم.

تعداد مسیرهای یکنوا در شبکه $(n - 1) \times (n + 1)$ برابر با $\binom{2n}{n-1}$ است. بیایید این مسیرها را مسیرهای «بد» بنامیم. در نتیجه، برای به دست آوردن تعداد مسیرهای یکنوایی که از قطر اصلی عبور نمی‌کنند، مسیرهای «بد» فوق را کم می‌کنیم و به فرمول زیر می‌رسیم:

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n + 1} \binom{2n}{n} , {n} \geq 0$$

مرجع

مسائل تمرینی