مقالات ریاضی با فرمت DOC صفحات 9
شاید در ریاضیات گسسته با مسأله ی زیر برخورد کرده باشید:
مسأله: یک صفحه ی شطرنجی n×n در نظر بگیرید؛ می‌خواهیم با حرکت روی خطوط صفحه ی شطرنجی، از نقطه ی A در گوشه ی سمت چپ پائین صفحه، E.C.Catalan
شروع کرده و به نقطه ی B در گوشه ی سمت راست بالای صفحه برسیم. شرط کار این است که فقط می‌توانیم به سمت‌های راست و بالا حرکت کنیم و هرگز نباید به بالای قطر AB برویم. به چند طریق می‌توان از A به B رسید؟
طرح این مسأله، انگیزه‌ای برای معرّفی مفاهیم زیر میباشد.
تعریف: برای ،n امین عدد کاتالان(ریاضی دان بلژیکی) عبارت است از: .
تعریف: همان‌طور که می‌دانیم هرکلمه از تعدادی حرف تشکیل شده است. اگر حرف‌های تشکیل‌دهنده ی کلمات را 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 است [چرا؟] .
اعداد کاتالان