ریاضیات قانون ذهن
صفحات وبلاگ
کلمات کلیدی مطالب
     
نویسنده: زهرا شريف زاده - ۱۳۸٩/٤/۱٦

 

به دنباله ی اعداد زیر توجه کنید :

....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) می باشد.

نویسندگان وبلاگ:
کدهای اضافی کاربر :