مقالات ریاضی با فرمت DOC صفحات 10
شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حرکت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، شروع کرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط کار این است که فقط می‌توانیم به سمت‌های راست و بالا حرکت کنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟
طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر می‌باشد.
تعریف: برای ،n امین عدد کاتالان(ریاضی دان بلژیکی) عبارت است از:
- C.Catalan
تعریف: همان‌طور که می‌دانیم هرکلمه از تعدادی حرف تشکیل شده است. اگر حرف‌های تشکیل‌دهنده ی کلمات را x و y بگیریم، یک کلمه‌ی Dyck به طول عبارت است از کلمه‌ای که از n تا x و n تا y تشکیل شده است و در هیچ قطعه‌ی آغازی کلمه، تعداد yها بیشتر از تعداد xها نمی‌باشد.
مثلاً: کلمه‌ی xyyx یک کلمه‌ی Dyck نمی‌باشد چون در قطعه‌ی آغازی xyy تعداد yها از تعداد xها بیشتر است. امّا xyxyxy یک کلمه‌ی Dyck است.
قرارداد: از این به بعد کلمه‌ی Dyck را با DW و کلمه‌ای که خاصیّت Dyck ندارد را با NDW نشان می‌دهیم.
اعداد کاتالان
