اختصاصی از
فایل هلپ دانلودمقاله اعداد کاتالان دانلود با لینک مستقیم و پر سرعت .
شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی 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 عوض کنیم پس کلمهای با 1-n تا x و 1+n تا y خواهیم داشت [چرا؟].
از طرفی اگر کلمهای دلخواه به طول متشکل از 1-n تا x و 1+n تا y داشته باشیم ،اولین قطعه ی آغازی این کلمه که تعداد y ها یکی بیش تر از تعداد x هاست در نظر بگیرید و تمامی y هایی که بعد از این قطعه ظاهر می شوند را با xو تمامی x ها را [در صورت وجود] با y عوض کنید. کلمهی حاصل یک NDW است [چرا؟] .
در واقع این روش یک تناظر یک به یک بین کلماتی به طول شامل 1-n تا x و 1+n تا y و NDWهای به طول برقرار میکند. چون به تعداد کلمه ی به طول شامل 1-n تا x و 1+n تا y داریم ، پس تعداد NDW های به طول برابر است با . امّا تعداد DWها برابر است با اختلاف تعداد کلّ کلمات و تعداد NDWها، پس :
تعداد DWهای به طول
اکنون به مسألهای که در آغاز مقاله مطرح کردیم، برمیگردیم.
اگر حرکت به سمت راست را با x و حرکت به سمت بالا را با y نشان دهیم پس تعداد راههای رسیدن از A به B [با توجه به شرط مسأله]برابر است با تعداد DWهای به طول که همانا میباشد.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 10 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود با لینک مستقیم
دانلودمقاله اعداد کاتالان