دانلود مقاله اعداد کاتالان
اعداد کاتالان
شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حرکت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع کرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط کار این است که فقط می‌توانیم به سمت‌های راست و بالا حرکت کنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟
طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر می‌باشد.
تعریف: برای ،n امین عدد کاتالان(ریاضی دان بلژیکی) عبارت است از:
E.C.Catalan
تعریف: همان‌طور که می‌دانیم هرکلمه از تعدادی حرف تشکیل شده است. اگر حرف‌های تشکیل‌دهنده ی کلمات را x و y بگیریم، یک کلمه‌ی Dyck به طول عبارت است از کلمه‌ای که از n تا x و n تا y تشکیل شده است و در هیچ قطعه‌ی آغازی کلمه، تعداد yها بیشتر از تعداد xها نمی‌باشد.
مثلاً: کلمه‌ی xyyx یک کلمه‌ی Dyck نمی‌باشد چون در قطعه‌ی آغازی xyy تعداد yها از تعداد xها بیشتر است. امّا xyxyxy یک کلمه‌ی Dyck است.
قرارداد: از این به بعد کلمه‌ی Dyck را با DW و کلمه‌ای که خاصیّت Dyck ندارد را با NDW نشان می‌دهیم.
مسأله: چند DW به طول می‌توان نوشت؟
حلّ: تعداد کلّ کلماتی به طول که می‌توان با n تا x و n تا y نوشت برابر است با .[چرا؟].از طرفی اگر یک NDW دلخواه در نظر بگیریم؛ پس یک قطعه‌ی آغازی از این کلمه وجود دارد که در آن تعداد yها بیشتر از تعداد xها است. اگر اوّلین قطعه‌ی آغازی که این شرط را دارد در نظر بگیریم و تمامی xهایی که پس از این قطعه ظاهر می‌شوند را با y و تمامی yها را [در صورت وجود] با x عوض کنیم پس کلمه‌ای با ۱-n تا x و ۱+n تا y خواهیم داشت [چرا؟].
از طرفی اگر کلمه‌ای دلخواه به طول متشکل از ۱-n تا x و ۱+n تا y داشته باشیم ،اولین قطعه ی آغازی این کلمه که تعداد y ها یکی بیش تر از تعداد x هاست در نظر بگیرید و تمامی y هایی که بعد از این قطعه ظاهر می شوند را با xو تمامی x ها را [در صورت وجود] با y عوض کنید. کلمه‌ی حاصل یک NDW است [چرا؟] .
در واقع این روش یک تناظر یک به یک بین کلماتی به طول شامل ۱-n تا x و ۱+n تا y و NDWهای به طول برقرار می‌کند. چون به تعداد کلمه ی به طول شامل ۱-n تا x و ۱+n تا y داریم ، پس تعداد NDW های به طول برابر است با . امّا تعداد DWها برابر است با اختلاف تعداد کلّ کلمات و تعداد NDWها، پس :
تعداد DWهای به طول
اکنون به مسأله‌ای که در آغاز مقاله مطرح کردیم، برمی‌گردیم.
اگر حرکت به سمت راست را با x و حرکت به سمت بالا را با y نشان دهیم پس تعداد راه‌های رسیدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهای به طول که همانا می‌باشد.
مسأله‌ای دیگر: به چند طریق می‌توان با n جفت پرانتز ( )؛ عبارتهای با معنی نوشت؟
مثلاً برای ۳و ۲و ۱=n داریم:
۱=n ( ) .
2=n (( )) و ( ) ( ) .
۳=n (( )) ( ) و ( ) (( )) و ( ) ( ) ( ) و ((( ))) و ( ( ) ( ) ) .
اگر به جای )، x و به جای (، y قرار دهیم آن‌گاه تعداد عبارتهای با معنی با n جفت پرانتز با تعداد DWهای به طول برابر خواهد بود و این یعنی برابر است.
تاکنون حلّ سه مسأله منجر به اعداد کاتالان شده است، در ذیل توجّه شما را به دو نمونه ی دیگر جلب می‌کنیم:
الف) تعداد راه‌های مختلف پرانتز‌گذاری بین ۱+n نماد ریاضی عبارت است از .
به عنوان مثال اگر a و b و c و d چهار نماد ریاضی باشند، روش‌های مختلف پرانتز‌گذاری بین آنها از این قرار است:
ب) یک ۲+n ضلعی محدّب در نظر بگیرید. با وصل کردن رأس‌ها، می‌توان این چند ضلعی را به مثلث‌هایی افراز کرد.
به عنوان مثال برای ۳=n داریم :
با توجه به روند مقاله،آیا می‌توانید تعداد راه های متفاوت افراز را حدس بزنید؟ بله درست حدس زدید، تعداد روش های متفاوت افراز عبارت است از .
اعداد کاتالان در مسأله های دیگری از جمله شمارش درخت ها در نظریه گراف یا شمارش نوع خاصی از افراز های مجموعه های متناهی نیز ظاهر می شوند .
مسأله‌ی اول – پرانتزهای بالانس
فرض کنید که n جفت پرانتز دارید و می‌خواهید از آنها دسته‌بندی‌های درستی بسازید. منظور از دسته‌بندی «درست» پرانتزها این است که برای هر پرانتز باز، یک پرانتز بسته وجود داشته باشد.
برای مثال (()()) یک دسته‌بندی درست و ())()( یک دسته‌بندی نادرست از پرانتزها است.
حال، مسأله این است که برای n جفت پرانتز، چند تا دسته‌بندی درست می‌توانیم انجام دهیم!؟
شاید توضیح دقیق‌تر مسأله به این صورت باشد که:
رشته‌ای از پرانتزها را «درست» می‌گوییم که در آن رشته، تعداد پرانتزهای باز با تعداد پرانتزهای بسته برابر باشد و هم‌چنین اگر از سمت چپ رشته شروع به حرکت کنیم و به‌سمت راست آن برویم به‌ازای هر پرانتز باز عدد ۱ بگذاریم و به‌ازای هر پرانتز بسته عدد ۱- بگذاریم در انتهایِ پیمودن رشته، جمع این اعداد «نامنفی» شود.
مسأله‌ی دوم – مثلث‌بندیِ چندضلعی‌ها
اگر تعداد راه‌های مثلث‌بندی کردن یک n+2 ضلعی منتظم را بشماریم دوباره به «اعداد کاتالان» دست می‌یابیم.
یاداوری – منظور از مثلث‌بندی کردن یک چند ضلعی منتظم، تقسیم آن چندضلعی به‌نواحی مثلثی شکل است.
در شکل ذیل مثلث‌بندی کردن ۳، ۴، ۵ و ۶ ضلعی منتظم نشان داده شده است.
همان‌طوری که می‌بینید ۱، ۲، ۵ و ۱۴راه برای این کار وجود دارد. برای دوضلعی منتظم هم مثلث‌بندی به ۱ راه ممکن است؛ پس می‌بینیم که برای n=0 نیز برقرار است.
مسأله‌ی سوم – درخت‌های دودویی
اعداد کاتالان هم‌چنین می‌توانند تعداد درختان دودویی ریشه‌دار با n گره داخلی (همه‌ی گره‌ها به‌جز ریشه) را بشمارند.
همان‌طور در شکل ذیل می‌بینید کلیه‌ی درخت‌های دودویی ریشه‌دار با ۰، ۱، ۲ و ۳ گره داخلی نشان داده شده است.
درخت دودویی ریشه‌دار، آرایشی از گره‌ها و یال‌هاست به‌طوری یک گره به‌خصوص وجود دارد که هیچ یالی به آن وارد نمی‌شود که به آن «ریشه» می‌گوییم و هرچه از ریشه‌ی پایین می‌آییم دو یا ۱ یا صفر یال وجود خواهد داشت. گره‌های داخلی آن‌هایی هستند که به دو گره دیگر وصل باشند.
مسأله‌ی چهارم – ترتیب ضرب
فرض کنید مجموعه‌ای از n+1 عدد دارید که می‌خواهید آنها را دو به دو در هم ضرب کنید؛ به این معنا که n عمل ضرب باید صورت بگیرد؛ بدون عوض کردن ترتیب خود اعداد، می‌توانید اعداد را به‌ترتیب‌های گوناگونی در هم ضرب کنید.
در این‌جا تعداد ترتیب‌های ممکن برای ضرب n بین ۰ تا ۴ آمده است.
برای تبدیل مثال بالا به نمادگذاری پرانتزی، این کار را انجام می دهی:
به‌جز نقطه (نشانه‌ی ضرب) و پرانتزهای بسته، همه‌چیز را پاک می‌کنیم و سپس به‌جای همه‌ی نقطه‌ها، «پرانتز باز» جایگزین می‌کنیم.
برای مثال: اگر بخواهیم این عمل را روی عبارت ذیل اعمال کنیم:
(a.(((b.c).d).e))
به این صورت عمل می‌کنیم که همه‌چیز به‌جز نقطه و پرانتز بسته‌ها را پاک می‌کنیم که عبارت به‌صورت ذیل در‌می‌آید.
..).).)).
سپس «نقطه‌ها» را با «پرانتز باز» جایگزین می‌کنیم. در نتیجه رشته‌ی ذیل حاصل می‌شود:
(()()())
پس می‌توان نتیجه گرفت راه‌حل این مسأله نیز «اعداد کاتالان» هستن!
از این دست مسائل – که راه‌حل آنها دنباله‌ی اعداد معروفی با نام «اعداد کاتالان» می‌باشد – بسیار است.
حال باید بدانیم این دنباله از اعداد از کجا آمده‌اند!؟
به‌دست آوردن جمله‌ی عمومی این دنباله‌ی اعداد دارای پیچیدگی‌هایی است که در این زنگ تفریح به آن نمی‌پردازیم بلکه فقط به بیان فرمول صریح (جمله‌ی عمومی) «اعداد کاتالان» بسنده می‌کنیم.
i اُمین عدد کاتالان از رابطه‌ی ذیل به‌دست می‌آید: