mathematics
23rd September 2010, 07:56 PM
شايد در رياضيات گسسته با مسأله ي زير برخورد كرده باشيد:
مسأله: يك صفحه ي شطرنجي n×n در نظر بگيريد؛ مي‌خواهيم با حركت روي خطوط صفحه ي شطرنجي، از نقطه ي A در گوشه ي سمت چپ پائين صفحه، شروع كرده و به نقطه ي B در گوشه ي سمت راست بالاي صفحه برسيم. شرط كار اين است كه فقط مي‌توانيم به سمت‌هاي راست و بالا حركت كنيم و هرگز نبايد به بالاي قطر AB برويم. به چند طريق مي‌توان از A به B رسيد؟
http://anjoman.ir/Images/Public/2007628112158_catal1.JPG
طرح اين مسأله، انگيزه‌اي براي معرّفي مفاهيم زير مي‌باشد.
تعريف: برايhttp://anjoman.ir/Images/Public/200762812345_cat1.gif ،n امين عدد كاتالان(رياضي دان بلژيكي) عبارت است از:http://anjoman.ir/Images/Public/2007628121917_cat2.gif
http://anjoman.ir/Images/Public/200763016510_ecatalan.jpg
E.C.Catalan
تعريف: همان‌طور كه مي‌دانيم هركلمه از تعدادي حرف تشكيل شده است. اگر حرف‌هاي تشكيل‌دهنده ي كلمات را x و y بگيريم، يك كلمه‌ي Dyck به طول2n عبارت است از كلمه‌اي كه از n تا x و n تا y تشكيل شده است و در هيچ قطعه‌ي آغازي كلمه، تعداد yها بيشتر از تعداد xها نمي‌باشد.
مثلاً: كلمه‌ي xyyx يك كلمه‌ي Dyck نمي‌باشد چون در قطعه‌ي آغازي xyy تعداد yها از تعداد xها بيشتر است. امّا xyxyxy يك كلمه‌ي Dyck است.
قرارداد: از اين به بعد كلمه‌ي Dyck را با DW و كلمه‌اي كه خاصيّت Dyck ندارد را با NDW نشان مي‌دهيم.
مسأله: چند DW به طول2n مي‌توان نوشت؟
حلّ: تعداد كلّ كلماتي به طول2n كه مي‌توان با n تا x و n تا y نوشت برابر است با http://anjoman.ir/Images/Public/200762812347_cat3.gif.[چرا؟].از طرفي اگر يك NDW دلخواه در نظر بگيريم؛ پس يك قطعه‌ي آغازي از اين كلمه وجود دارد كه در آن تعداد yها بيشتر از تعداد xها است. اگر اوّلين قطعه‌ي آغازي كه اين شرط را دارد در نظر بگيريم و تمامي xهايي كه پس از اين قطعه ظاهر مي‌شوند را با y و تمامي yها را [در صورت وجود] با x عوض كنيم پس كلمه‌اي با 1-n تا x و 1+n تا y خواهيم داشت [چرا؟].
از طرفي اگر كلمه‌اي دلخواه به طول2nمتشكل از 1-n تا x و 1+n تا y داشته باشيم ،اولين قطعه ي آغازي اين كلمه كه تعداد y ها يكي بيش تر از تعداد x هاست در نظر بگيريد و تمامي y هايي كه بعد از اين قطعه ظاهر مي شوند را با xو تمامي x ها را [در صورت وجود] با y عوض كنيد. كلمه‌ي حاصل يك NDW است [چرا؟] .
در واقع اين روش يك تناظر يك به يك بين كلماتي به طول2nشامل 1-n تا x و 1+n تا y و NDWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPG برقرار مي‌كند. چون به تعداد http://anjoman.ir/Images/Public/2007628124452_cat4.gifكلمه ي به طولhttp://anjoman.ir/Images/Public/2007628122612_catal2.JPG شامل 1-n تا x و 1+n تا y داريم ، پس تعداد NDW هاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPG برابر است با . امّا تعداد DWها برابر است با http://anjoman.ir/Images/Public/2007628124452_cat4.gifاختلاف تعداد كلّ كلمات و تعداد NDWها، پس :
http://anjoman.ir/Images/Public/2007628125237_cat5.gif تعداد DWهاي به طولhttp://anjoman.ir/Images/Public/2007628122612_catal2.JPG
اكنون به مسأله‌اي كه در آغاز مقاله مطرح كرديم، برمي‌گرديم.
اگر حركت به سمت راست را با x و حركت به سمت بالا را با y نشان دهيم پس تعداد راه‌هاي رسيدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPGكه همانا http://anjoman.ir/Images/Public/2007630143835_cat6.gif مي‌باشد.
مسأله‌اي ديگر: به چند طريق مي‌توان با n جفت پرانتز ( )؛ عبارتهاي با معني نوشت؟
مثلاً براي 3و 2و 1=n داريم:
1=n ( ) .
2=n (( )) و ( ) ( ) .
3=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جاي )، x و به جاي (، y قرار دهيم آن‌گاه تعداد عبارتهاي با معني با n جفت پرانتز با تعداد DWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPGبرابر خواهد بود و اين يعني برابر http://anjoman.ir/Images/Public/2007630143835_cat6.gifاست.
تاكنون حلّ سه مسأله منجر به اعداد كاتالان شده است، در ذيل توجّه شما را به دو نمونه ي ديگر جلب مي‌كنيم:
الف) تعداد راه‌هاي مختلف پرانتز‌گذاري بين 1+n نماد رياضي عبارت است از http://anjoman.ir/Images/Public/2007630143835_cat6.gif.
به عنوان مثال اگر a و b و c و d چهار نماد رياضي باشند، روش‌هاي مختلف پرانتز‌گذاري بين آن‌ها از اين قرار است:
http://anjoman.ir/Images/Public/2007628125837_catal3.JPG
ب) يك 2+n ضلعي محدّب در نظر بگيريد. با وصل كردن رأس‌ها، مي‌توان اين چند ضلعي را به مثلث‌هايي افراز كرد.
به عنوان مثال براي 3=n داريم :
http://anjoman.ir/Images/Public/200763015451_cat7.gif
با توجه به روند مقاله،آيا مي‌توانيد تعداد راه هاي متفاوت افراز را حدس بزنيد؟ بله درست حدس زديد، تعداد روش هاي متفاوت افراز عبارت است از http://anjoman.ir/Images/Public/2007630143835_cat6.gif .
اعداد كاتالان در مسأله هاي ديگري از جمله شمارش درخت ها در نظريه گراف يا شمارش نوع خاصي از افراز هاي مجموعه هاي متناهي نيز ظاهر مي شوند .
مسأله: يك صفحه ي شطرنجي n×n در نظر بگيريد؛ مي‌خواهيم با حركت روي خطوط صفحه ي شطرنجي، از نقطه ي A در گوشه ي سمت چپ پائين صفحه، شروع كرده و به نقطه ي B در گوشه ي سمت راست بالاي صفحه برسيم. شرط كار اين است كه فقط مي‌توانيم به سمت‌هاي راست و بالا حركت كنيم و هرگز نبايد به بالاي قطر AB برويم. به چند طريق مي‌توان از A به B رسيد؟
http://anjoman.ir/Images/Public/2007628112158_catal1.JPG
طرح اين مسأله، انگيزه‌اي براي معرّفي مفاهيم زير مي‌باشد.
تعريف: برايhttp://anjoman.ir/Images/Public/200762812345_cat1.gif ،n امين عدد كاتالان(رياضي دان بلژيكي) عبارت است از:http://anjoman.ir/Images/Public/2007628121917_cat2.gif
http://anjoman.ir/Images/Public/200763016510_ecatalan.jpg
E.C.Catalan
تعريف: همان‌طور كه مي‌دانيم هركلمه از تعدادي حرف تشكيل شده است. اگر حرف‌هاي تشكيل‌دهنده ي كلمات را x و y بگيريم، يك كلمه‌ي Dyck به طول2n عبارت است از كلمه‌اي كه از n تا x و n تا y تشكيل شده است و در هيچ قطعه‌ي آغازي كلمه، تعداد yها بيشتر از تعداد xها نمي‌باشد.
مثلاً: كلمه‌ي xyyx يك كلمه‌ي Dyck نمي‌باشد چون در قطعه‌ي آغازي xyy تعداد yها از تعداد xها بيشتر است. امّا xyxyxy يك كلمه‌ي Dyck است.
قرارداد: از اين به بعد كلمه‌ي Dyck را با DW و كلمه‌اي كه خاصيّت Dyck ندارد را با NDW نشان مي‌دهيم.
مسأله: چند DW به طول2n مي‌توان نوشت؟
حلّ: تعداد كلّ كلماتي به طول2n كه مي‌توان با n تا x و n تا y نوشت برابر است با http://anjoman.ir/Images/Public/200762812347_cat3.gif.[چرا؟].از طرفي اگر يك NDW دلخواه در نظر بگيريم؛ پس يك قطعه‌ي آغازي از اين كلمه وجود دارد كه در آن تعداد yها بيشتر از تعداد xها است. اگر اوّلين قطعه‌ي آغازي كه اين شرط را دارد در نظر بگيريم و تمامي xهايي كه پس از اين قطعه ظاهر مي‌شوند را با y و تمامي yها را [در صورت وجود] با x عوض كنيم پس كلمه‌اي با 1-n تا x و 1+n تا y خواهيم داشت [چرا؟].
از طرفي اگر كلمه‌اي دلخواه به طول2nمتشكل از 1-n تا x و 1+n تا y داشته باشيم ،اولين قطعه ي آغازي اين كلمه كه تعداد y ها يكي بيش تر از تعداد x هاست در نظر بگيريد و تمامي y هايي كه بعد از اين قطعه ظاهر مي شوند را با xو تمامي x ها را [در صورت وجود] با y عوض كنيد. كلمه‌ي حاصل يك NDW است [چرا؟] .
در واقع اين روش يك تناظر يك به يك بين كلماتي به طول2nشامل 1-n تا x و 1+n تا y و NDWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPG برقرار مي‌كند. چون به تعداد http://anjoman.ir/Images/Public/2007628124452_cat4.gifكلمه ي به طولhttp://anjoman.ir/Images/Public/2007628122612_catal2.JPG شامل 1-n تا x و 1+n تا y داريم ، پس تعداد NDW هاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPG برابر است با . امّا تعداد DWها برابر است با http://anjoman.ir/Images/Public/2007628124452_cat4.gifاختلاف تعداد كلّ كلمات و تعداد NDWها، پس :
http://anjoman.ir/Images/Public/2007628125237_cat5.gif تعداد DWهاي به طولhttp://anjoman.ir/Images/Public/2007628122612_catal2.JPG
اكنون به مسأله‌اي كه در آغاز مقاله مطرح كرديم، برمي‌گرديم.
اگر حركت به سمت راست را با x و حركت به سمت بالا را با y نشان دهيم پس تعداد راه‌هاي رسيدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPGكه همانا http://anjoman.ir/Images/Public/2007630143835_cat6.gif مي‌باشد.
مسأله‌اي ديگر: به چند طريق مي‌توان با n جفت پرانتز ( )؛ عبارتهاي با معني نوشت؟
مثلاً براي 3و 2و 1=n داريم:
1=n ( ) .
2=n (( )) و ( ) ( ) .
3=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جاي )، x و به جاي (، y قرار دهيم آن‌گاه تعداد عبارتهاي با معني با n جفت پرانتز با تعداد DWهاي به طول http://anjoman.ir/Images/Public/2007628122612_catal2.JPGبرابر خواهد بود و اين يعني برابر http://anjoman.ir/Images/Public/2007630143835_cat6.gifاست.
تاكنون حلّ سه مسأله منجر به اعداد كاتالان شده است، در ذيل توجّه شما را به دو نمونه ي ديگر جلب مي‌كنيم:
الف) تعداد راه‌هاي مختلف پرانتز‌گذاري بين 1+n نماد رياضي عبارت است از http://anjoman.ir/Images/Public/2007630143835_cat6.gif.
به عنوان مثال اگر a و b و c و d چهار نماد رياضي باشند، روش‌هاي مختلف پرانتز‌گذاري بين آن‌ها از اين قرار است:
http://anjoman.ir/Images/Public/2007628125837_catal3.JPG
ب) يك 2+n ضلعي محدّب در نظر بگيريد. با وصل كردن رأس‌ها، مي‌توان اين چند ضلعي را به مثلث‌هايي افراز كرد.
به عنوان مثال براي 3=n داريم :
http://anjoman.ir/Images/Public/200763015451_cat7.gif
با توجه به روند مقاله،آيا مي‌توانيد تعداد راه هاي متفاوت افراز را حدس بزنيد؟ بله درست حدس زديد، تعداد روش هاي متفاوت افراز عبارت است از http://anjoman.ir/Images/Public/2007630143835_cat6.gif .
اعداد كاتالان در مسأله هاي ديگري از جمله شمارش درخت ها در نظريه گراف يا شمارش نوع خاصي از افراز هاي مجموعه هاي متناهي نيز ظاهر مي شوند .