ahmadfononi
معاونت انجمن
....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) می باشد.