به دنباله ی اعداد زیر توجه کنید :
....1،1،2،5،14،42
به نظر شما چه رابطه ای بیانگر این دنباله می باشد...
برای اینکه رابطه ی بین اعداد بالا را درک کنیم از یک مثال جالب بهره می بریم.
مجموعه ای از مسایل وجود دارند که دارای راه حلی کاملا مشابه هستند یعنی جواب همه ی آنها دنباله ای از اعداد موسوم بهاعداد کاتالان(Catalan Numbers) هستند.
پرانتزهای متوازن (Balanced Parentheses)
فرض کنید که n جفت پرانتز داریم و قصد داریم که آنها را به گونه ای معتبر (valid)بچینیم منظور از چینش معتبر این است که به ازای هر پرانتز باز یک پرانتز بسته(جفت) موجود باشد . برای نمونه "(()())" معتبر است اما ")()(()" خیر.پرسش این است که چند گونه چینش معتبر برای هر n جفت موجود است؟
شاید یک تعریف دقیقتر مسئله این گونه باشد:
رشته ای از پرانتز ها معتبر است که اگر تعداد مساوی از پرانتز های باز و بسته موجود باشد و اگر از چپ این گونه آغاز کنیم و به راست برویم که:
اضافه کنیم عدد 1 را هر گاه یک پرانتز باز و کم کنیم عدد 1 را هر گاه پرانتز بسته ای ایجاد کردیم : سرانجام این جمع و تفریق منفی نخواهد بود!
جدول زیر یافتن تعداد چینش ها به گونه ای دستی و با یافتن همه ی حالات است که به دلیل رشد ناگهانی این حالات( ذات اعداد کاتالان) تا تعداد n=5 بیشتر نرفته.
|
n = 0:
|
* |
1 way
|
|
n = 1:
|
() |
1 way
|
|
n = 2:
|
()(), (()) |
2 ways
|
|
n = 3:
|
()()(), ()(()), (())(), (()()), ((())) |
5 ways
|
|
n = 4:
|
()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((())))
|
14 ways |
|
n = 5:
|
()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()((()))(), ()(()()()), ()(()(())), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), ((()))()(), ((()))(()), (()()())(), (()(()))(), ((())())(), ((()()))(), (((())))(), (()()()()), (()()(())), (()(())()), (()(()())), (()((()))), ((())()()), ((())(())), ((()())()), (((()))()), ((()()())), ((()(()))), (((())())),(((()()))), ((((()))))
|
42 ways |
برای n=0(تعداد جفت پرانتز برابر صفر) تعداد حالات چینش را 1 در نظر گرفتیم توجه داشته باشیم که در این حالت تنها یک حالت یعنی "هیچ گونه چینشی موجود نیست " موجود است!
نمونه هایی دیگر از این دست مسایل که دارای چنین پاسخ مشابهی هستند عبارتند از:
-Polygon Triangulation ( مثلث بندی کردن چند ضلعی ها)
-Hands Across a Table(دست دادن دور میز به گونه ای که هیچ دو دستی باهم برخورد نکند)
-Binary Trees(درختان دودویی)
-Multiplication Orderings(ترتیبهای ضرب کردن که بسیار مشابه با مسئله ی پرانتزهاست)
و...
اما همانطور که شاهدیم به دست آوردن کل حالات حتی برای n های بزرگتر از 4 نیز بسیار سخت است .
در اینجا تنها این را ذکر کنم که این مسئله یک تعریف بازگشتی(Recursive Definition) دارد و پس از یک سری محاسبات کمی زیاد به نتیجهی
زیر می رسیم:
i امین عدد کاتالان با فرمول زیر محاسبه می شود:
Ci=[1/(i+1)]C(2i,i)
توجه کنید که Ci عدد کاتالان i ام
و C درون فرمول نشانه ی ترکیب (Combination) می باشد.
عدد پی 
