מספרי קטלן - חישוב כמות המספריים הטבעיים עם תכונה מסוימת

היי גלעד,
תחילה, נראה כי הבעיה הינה בייקציה (התאמה חח"ע ועל) לקבוצת סדרות מאוזנות של n זוגות סוגריים. נחליף את הספרות האי-זוגיות בפותח ואת הספרות הזוגיות בסוגר. מספר הדרכים לקבל סדרה מאוזנת של 5n פותחים ו-5n סוגרים ימניים הוא מספר קטלן C_{5n}. עתה עלינו להחליף חזרה את הסוגרים השמאליים בספרות האי-זוגיות. מספר הדרכים לעשות זאת הוא ע"פ המקדם המולטינומי:

{5n \choose n,n,n,n,n}

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

C_{5n}\cdot{5n \choose n,n,n,n,n}^{2}