מספרי קטלן - מספר המסלולים על סולם

[Gilad]

שלום לכולם, די חלוד עם מספרי קטלן. אשמח לעזרה עם השאלה הבאה:

אדם ניצב ליד סולם בן 20 שלבים הנשען על קיר. כאשר האדם עומד על הקרקע הוא יכול בצעד הבא רק לעלות שלב. כאשר הוא ניצב על שלב 20 הוא יכול בצעד הבא רק לרדת שלב. כאשר האדם ניצב על כל שלב אחר, הוא יכול בצעד הבא לעלות או לרדת שלב.

1. בכמה אופנים יכול האדם לעשות 40 צעדים ולסיים חזרה על הקרקע?
2. בכמה אופנים יכול האדם לעשות 44 צעדים ולסיים חזרה על הקרקע?
3. בכמה אופנים יכול האדם לעשות 35 צעדים ולסיים חזרה על הקרקע?

תודה לכולם על העזרה.

[Zeta]

נפתור את הסעיפים:

א. אדם מבצע 40 צעדים, כלומר 20 צעדים מעלה ו-20 צעדים מעטה (בסדר חוקי כלשהו).
נתרגם את הבעיה, לבעיית המסלולים על השריג: כל צעד למעלה בסולם מתורגם למעלה בשריג, וכל צעד למטה בסולם מתורגם לצעד ימינה בשריג. סה"כ יש 20 צעדים מכל סוג. נבדוק את התנאים:

• תנאי ראשון: אסור לעשות צעד למטה כשעומדים בתחתית הסולם. זאת כמו בשריג, שאסור לרדת מתחת לאלכסון.

• תנאי שני: אסור לעשות צעדים למעלה כשעומדים בראש הסולם. נשים לב כי מאחר ומדובר ב-40 צעדים סה"כ, נוכל להסיק כי אם האדם ינסה לבצע יותר מ-20 צעדים למעלה, הוא לא יוכל לחזור ב-20 צעדים לקרקע.

לפיכך נובע כי מספר האופנים הוא כמספר מסלולי השריג מ-(0,0) ל-(20,20) שאינם יורדים מתחת לאלכסון הראשי, כלומר C_{20} אפשרויות.

ב. אדם מבצע 44 צעדים, כלומר 22 צעדים מעלה ו-22 צעדים מעטה (בסדר חוקי כלשהו). נבדוק את התנאים:

• תנאי ראשון: כמו בסעיף הקודם, לא ניתן לעשות צעד למטה כשעומדים בתחת הסולם, וזאת בדומה לבעיית השריג, שלא ניתן לרדת מתחת לאלכסון.

• תנאי שני: אסור לעשות צעדים למעלה כשעומדים בראש הסולם. אולם בשונה מהסעיף הקודם, הפעם כאשר מגיעים לראש הסולם, יכול להיות מצב שעדיין נשארו צעדים למעלה. ע"י תרגום של הבעיה לבעיית השריג, נובע כי אסור לעבור בנקודות שההפרש בין הערך האנכי לערך האופקי גדול מ-20. כלומר המסלולים הבעתיים הם (0,21) ו- (1,22).

נעזר בעיקרון הכלה והפרדה:
עולם: כל המסלולים החוקיים שלא יורדים מתחת לאלכסון הראשי.
תכונות: נגדיר את שתי התכונות הבאות:

• תכונה P_{1} - המסלול העובר בנקודה (0,21) ולא יורד מתחת לאלכסון הראשי.
• תכונה P_{2} - המסלול העובר בנקודה (1,22) ולא יורד מתחת לאלכסון הראשי.

קודם כל, נשים לב כי מספר המסלולים החוקיים אשר אינם יורדים מתחת לאלכסון הראשי הינו

W(0)=C_{22}

מספר המסלולים מ-(0,0) ל- (0,21) הינו {21 \choose 0} ומספר המסלולים מ-(0,21) ל-(22,22) הינו {23 \choose 1}. לפיכך נקבל:

W(P_{1})=W(P_{2})=22\Longrightarrow W(1)=2\cdot 22=44

ברור כי W(2)=W(P_{1},P_{2})=2 שכן קיימים רק שני מסלולים העוברים דרך שתי הנקודות (0,21) ו-(1,22). סה"כ נקבל:

E(0)=W(0)-W(1)+W(2)=C_{22}-44+2=C_{22}-42

ג. על מנת לחזור אל נקודת ההתחלה, המסלול חייב להיות מורכב ממספר שווה של צעדים למעלה וצעדים למעטה, כלומר הסכום של מספר המסלולים, חייב להיות זוגי. מאחר והאדם מעוניין לבצע מספר אי-זוגי של צעדים, נוכל להסיק כי מספר האופנים הוא אפס.

מקווה שמובן, בהצלחה