اعداد کاتالان

اختصاصی از فایلکو اعداد کاتالان دانلود با لینک مستقیم و پر سرعت .

مقالات  ریاضی  با فرمت           DOC           صفحات  10

شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:

مسأله: یک صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حرکت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع کرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط کار این است که فقط می‌توانیم به سمت‌های راست و بالا حرکت کنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟

طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر می‌باشد.

تعریف: برای ،n امین عدد کاتالان(ریاضی دان بلژیکی) عبارت است از:

1. C.Catalan

تعریف: همان‌طور که می‌دانیم هرکلمه از تعدادی حرف تشکیل شده است. اگر حرف‌های تشکیل‌دهنده ی کلمات را x و y بگیریم، یک کلمه‌ی Dyck به طول  عبارت است از کلمه‌ای که از n تا x و n تا y تشکیل شده است و در هیچ قطعه‌ی آغازی کلمه، تعداد yها بیش‌تر از تعداد xها نمی‌باشد.

مثلاً: کلمه‌ی xyyx یک کلمه‌ی Dyck نمی‌باشد چون در قطعه‌ی آغازی xyy تعداد yها از تعداد xها بیش‌‌تر است. امّا xyxyxy یک کلمه‌ی Dyck است.

قرارداد: از این به بعد کلمه‌ی Dyck را با DW و کلمه‌ای که خاصیّت Dyck ندارد را با NDW نشان می‌دهیم.