מספרי קטלן
מבוא
אם אני אלך ברחוב ואשאל באקראי אנשים איזו סדרה מתמטית הם מכירים, אחרי שנקלף את שכבות האלו שיבהלו ויברחו או יתחכמו ויגידו ש-Numb3rs (אף אחד לא יגיד, העולם כבר שכח שהייתה סדרה כזו וגם לי לא יצא לראות אותה) כנראה אקבל שלל תשובות: “סדרת פיבונאצ’י”, “סדרת פיבונאצ’י!”, “פיבונאצ’י”, “הטבעיים” (חכמולוג, לסנן) ו”פיבונאצ’י”. ובכן, סדרת פיבונאצ’י כבודה במקומו מונח, יש עוד סדרות מעניינות בעולם ואני רוצה לדבר בפוסט הזה על אחת אהובה במיוחד - סדרת מספרי קטלן (Catalan, על שם המתמטיקאי הבלגי אז’ן שרל קטלן). זו הסדרה הבאה:
\( 1,1,2,5,14,42,132,429,1430,4862,\ldots \)
מה שמעניין בה הוא שהיא הפתרון של שלל בעיות קומבינטורית שונות ומשונות. המתמטיקאי ריצ’רד סטנלי (שכתב את הספר הפנטסטי Enumerative Combinatorics) התמחה בלאסוף בעיות שונות ומשונות שמספרי קטלן הם הפתרון שלהן, ובסופו של דבר פרסם ספר עם 214 בעיות כאלו. מן הסתם אני לא אכסה כמעט כלום מזה הפעם; אבל אני רוצה בפוסט הזה שנכיר את התכונות הבסיסיות של המספרים הללו (שאנחנו מבינים די טוב) ונראה שלל בעיות שונות ומשונות ולכאורה לא קשורות שהם פותרים.
היסטורית, האדם הראשון שיש לנו אינדיקציה שנתקל במספרי קטלן הוא המתמטיקאי המונגולי Minggatu, בספר על חישוב קירובים שכתב בסביבות 1730 שבו מספרי קטלן הופיעו בתוך חלק מהנוסחאות; זה פחות רלוונטי לנו כאן כי זה לא שימוש במספרי קטלן לפתרון בעיה קומבינטורית. מכאן אנחנו קופצים ל-1751, כשלאונרד אוילר (מהמתמטיקאים הפורים בהיסטוריה שנראה שהתעסק פשוט בכל דבר) תיאר אותם במכתב לשותפו המתמטי כריסטיאן גולדבך, בתור הפתרון של בעיה קומבינטורית ספציפית - אז בואו נתחיל מלדבר על הבעיה הזו למרות שהיא אולי לא הכי פשוטה מבין אלו שאפשר לפתוח בהן.
שילושים של מצולע
במקרה הזה תמונה אחת שווה אלף מילים, ואני מתנצל בפני מי שלא יכולים לראות אותה (ואת כל יתר האיורים שהפוסט הזה יהיה עמוס בהם):
מה רואים פה? אני מצייר משושה משוכלל (כלומר מצולע עם שש צלעות שאורכי כל הצלעות שלו שווים וכל הזוויות שלו שוות) ובתוך המשושה אני מותח קווים בין חלק מהקודקודים, בצורה כזו שאין שני קווים שחוצים אחד את השני, ואני מותח מספיק קווים כדי לחלק את המצולע למשולשים. דבר כזה נקרא “שילוש”. בימינו אנו שילושים הם דבר מאוד מעניין, למשל בגרפיקה תלת ממדית, אבל כבר בימי אוילר זה היה מספיק מעניין כדי לנסות להבין איך נראים השילושים האפשריים השונים של מצולע - ובפרט, כמה כאלו יש. מה שאנחנו רואים בתמונה הוא את כל 14 השילושים האפשריים של משושה משוכלל. חלק מהשילושים נראים דומים אחד לשני - כאילו אפשר לסובב או לשקף אחד ולקבל את האחר. מה שמעניין אותנו כאן הוא לספור אותם בתור שילושים שונים - כלומר, אפשר לחשוב על זה כאילו מספרנו את הקודקודים של המצולע, ואנחנו מסתכלים על רשימה של שלשות שמציינות קודקודים. הנה דוגמא:
כאן מספרתי את הקודקודים מ-1 עד 6 בכיוון השעון החל מהקודקוד העליון השמאלי, והמשולשים שלי הם \( \left\{ 1,5,6\right\} ,\left\{ 1,2,5\right\} ,\left\{ 2,4,5\right\} ,\left\{ 2,3,4\right\} \).
האם יש דרך מסודרת “לייצר” שילושים? למרבה השמחה, כן - דרך רקורסיבית. כלומר, אם אנחנו כבר יודעים למצוא שילושים למצולעים פשוטים, אנחנו יכולים לנצל את זה כדי למצוא שילושים למצולעים מורכבים יותר. מה המצולעים הפשוטים ביותר? ובכן, כמובן שמשולש הוא די פשוט - אם יש לנו משולש, ה”שילוש” שלו זה בסך הכל הוא עצמו. שימו לב שזה לא צריך להיות משולש משוכלל (“משולש שווה צלעות”) - זה נכון לכל משולש.
אבל חוץ ממשולש, תכף נראה שישתלם לנו לדבר על מצולע אפילו עוד יותר פשוט - מצולע בן שני קודקודים. מה זה הדבר הזה? זה בסך הכל קו ישר אחד; אפשר להתלונן ולומר שזה לא באמת מצולע, אבל זה לא משנה - כאמור, זה הולך להשתלם לנו לחשוב עליו כמצולע עוד מעט.
בואו ננסה למצוא שילוש למשושה המשוכלל. אני מתחיל עם השאלה - מה קורה עם הצלע 1-2? אני יודע שבסופו של דבר היא תהיה חלק ממשולש שכל הקודקודים שלו שייכים למצולע המקורי, כלומר משולש ששניים מהקודקודים שלו הם 1 ו-2 ואני חופשי לבחור את הקודקוד הנוסף - כל בחירה שונה תניב בסופו של דבר שילושים שונים. בואו נאמר שבחרתי את 5, אז אני מותח קווים אליו מ-1 ו-2, ומקבל:
עכשיו מגיע הצעד הרקורסיבי: קונספטואלית, אפשר לחשוב על זה כאילו אני מוחק את הצלע 1-2 מהמשושה ומקבל:
מה שקיבלתי פה הוא שפירקתי את המשושה המקורי לשני מצולעים שונים: המצולע 1-5-6 והמצולע 2-3-4-5. שני המצולעים חולקים קודקוד משותף אחד, את 5 - הקודקוד שבחרתי. בנוסף, יש להם פחות צלעות: לאחד יש 3 ולשני 4 (שימו לב שמספר הצלעות הכולל שלהם הוא כמספר הצלעות במצולע שהתחלנו ממנו, ועוד 1 - זה בגלל שמחקנו את 1-2 אבל הוספנו את 1-5 ואת 2-5). אם יש להם פחות צלעות, אני יכול רקורסיבית לשלש אותם… רגע, שניה, הרי 2-3-4-5 הוא אמנם מצולע, אבל הוא לא מצולע משוכלל, הוא נראה כמו מין טרפז שכזה. למה שאוכל לשלש אותו?
בואו נחשוב שניה - מה אנחנו צריכים כדי שנוכל לשלש צורה? ראינו שכל משולש הוא בר-שילוש, אבל מה קורה בצורה מורכבת יותר? במשושה שלנו הייתה לי הנחה סמויה - שאני באמת יכול להעביר קווים מ-1 ו-2 אל 5. לא הייתה לי בעיה לעשות את זה כי משושה משוכלל הוא צורה קמורה - כלומר, צורה שבה כל קו בין שתי נקודות ששייכות לצורה עובר כולו בתוך הצורה. זו ההנחה שאני זקוק לה - כלומר, מה שאני סופר הוא כמה שילושים יש למצולע קמור כלשהו, ויוצא שזה לא באמת תלוי בצורה של המצולע אלא רק במספר הקודקודים שלו.
בואו נכנס סימון לעניין: נסמן ב-\( T_{n} \) את מספר השילושים של מצולע קמור עם \( n \) קודקודים. הספירה שלנו מתחילה מ-2, ואז אמרנו שאני בוחר בצורה שנראית קצת שרירותית להגדיר \( T_{2}=1 \). בנוסף \( T_{3}=1 \) כי למשולש יש שילוש יחיד. ומה קורה עבור \( n \) גדולים יותר? אני אעשה את הטריק שכבר ראינו: אסתכל על הקודקודים 1,2 במצולע בן \( n \) הצלעות שלי, ואשאל את עצמי מי הקודקוד הנוסף שמתחבר אליהם. נסמן את הקודקוד הזה ב-\( k \) (\( 3\le k\le n \)). אחרי שנחבר את 1,2 אליו ונסיר את הקשת 1-2 נקבל שני מצולעים עם פחות צלעות. כמה צלעות? ובכן, בואו נסתכל על הדוגמא למעלה - שם בחרתי \( k=5 \), מה שאמר שהמצולע הראשון שקיבלנו כלל את הקודקודים \( 2,3,4,5 \) והמצולע השני את \( 5,6,1 \). זה מה שקורה באופן כללי - המצולעים שלנו יהיו בעלי קבוצות הקודקודים
\( \left\{ 2,3,\ldots,k\right\} ,\left\{ k,k+1,\ldots,n,1\right\} \)
בקבוצה הראשונה יש \( k-1 \) קודקודים ובשתיהן יחד יש \( n+1 \) קודקודים (כי \( k \) מופיע פעמיים) ולכן בקבוצה השניה יש \( \left(n+1\right)-\left(k-1\right) \) קודקודים. זה אומר שמספר השילושים האפשרי של המצולע הראשון הוא \( T_{k-1} \) ושל השני הוא \( T_{\left(n+1\right)-\left(k-1\right)} \). עכשיו נשתמש בקומבינטוריקה: כל שילוש של המצולע המקורי שלנו מתקבל מבחירה של שילוש אחד של המצולע הראשון ושילוש אחד של המצולע השני, ושתי הבחירות הללו הן בלתי תלויות זו בזו (כלומר, לכל שילוש של המצולע הראשון אפשר לבחור כל שילוש של המצולע השני ונקבל שילוש שונה של המצולע המקורי) ולכן מספר האפשרויות הכולל הוא מכפלה של מספר האפשרויות הראשון ומספר האפשרויות השני - זה מה שנקרא בקומבינטוריקה עקרון הכפל. בסך הכל יש \( T_{k-1}\cdot T_{\left(n+1\right)-\left(k-1\right)} \) אפשרויות.
עכשיו, זה היה מספר האפשרויות אם המשולש שאני בונה עם 1,2 כולל גם את \( k \). עבור בחירות שונות של \( k \) אני אקבל שילושים שונים. האם אותו ניתוח יעבוד בכולן? נראה שכן, אבל כדי לוודא בואו נסתכל על המקרה הקיצוני - נאמר, כשבוחרים את הקודקוד \( k=6 \):
למה זה המקרה הקיצוני? כי אם עכשיו אני מסיר את הצלע 1-2 אני מקבל “מצולע” בעל שני קודקודים, \( \left\{ 1,6\right\} \):
אבל זו בדיוק הסיבה שבגללה אמרתי קודם שנוח לי לחשוב גם על המקרה הזה בתור מצולע, עם שילוש יחיד. למי שהגישה הזו מפריעה לו אפשר לנסח עוד דרכים לחשוב על זה - למשל, שאנחנו פשוט גוזרים את כל המשולש 1-2-6 מהמצולע ונשארנו רק עם מצולע יחיד להתמודד איתו. זה לא באמת משנה - השורה התחתונה היא שאני מקבל \( T_{k-1}\cdot T_{\left(n+1\right)-\left(k-1\right)} \) אפשרויות תמיד, לכל \( k \), כולל מקרי הקיצון של \( k=3 \) ו-\( k=n \).
אם כך, אפשר לחשוב על בניית שילוש של מצולע בתור תהליך שבו אנחנו בוחרים \( k \), ועבור ה-\( k \) שבחרנו יש לנו \( T_{k-1}\cdot T_{\left(n+1\right)-\left(k-1\right)} \) אפשרויות לבנות שילוש. כאן זה לא תהליך דו-שלבי אלא סיטואציה של “או זה, או זה, או זה”. במקרה הזה עקרון החיבור בקומבינטוריקה אומר שאנחנו צריכים לחבר את מספר האפשרויות בכל אחד מהמקרים. אצלנו \( 3\le k\le n \) ולכן בסך הכל קיבלנו את הנוסחה
\( T_{n}=\sum_{k=3}^{n}T_{k-1}T_{\left(n+1\right)-\left(k-1\right)} \)
מה שאני אוהב בנוסחה הזו הוא שברור לנו איך היא התקבלה. הבעיה היא שהיא לא יפה במיוחד - יש קטסטרופה שלמה עם האינדקסים שם. אז המתמטיקאים אומרים - היי, בעצם, סדרת ה-\( T \)-ים הזו “מבזבזת” את שני האינדקסים הראשונים של, \( T_{0},T_{1} \) שבכלל לא מוגדרים. בואו נשנה סימון ונתחיל עם סדרה שכן מתחילה מאפס. נסמן ב-\( C \) את האיברים שלה, כלומר \( C_{0}=T_{2} \) ו-\( C_{1}=T_{3} \) וכדומה - באופן כללי, \( C_{n}=T_{n+2} \). אז נוסחת הנסיגה תהפוך להיות:
\( C_{n}=T_{n+2}=\sum_{k=3}^{n+2}T_{k-1}T_{\left(n+3\right)-\left(k-1\right)}=\sum_{k=3}^{n+2}C_{k-3}C_{\left(n+1\right)-\left(k-1\right)}= \)
\( =\sum_{i=0}^{n-1}C_{i}C_{n+1-\left(i+2\right)}=\sum_{i=0}^{n-1}C_{i}C_{n-1-i} \)
כאן השתמשתי בשינוי האינדקס \( i=k-3 \) כדי לפשט עוד יותר, ויש כאלו שכדאי שהנוסחה תהיה עוד יותר פשוטה מעדיפים להציג אותה ככה, עם \( C_{n+1} \) במקום \( C_{n} \):
\( C_{n+1}=\sum_{i=0}^{n}C_{i}C_{n-i} \)
זו נוסחת הנסיגה המהותית שמגדירה את מספרי קטלן, והיא מה שאוילר מצא (והסיק ממנה את מה שנקרא הפונקציה היוצרת של הסדרה ובשיטות מפוקפקות של חשבון דיפרנציאלי ואינטגרלי הסיק ממנה את הנוסחה הסגורה של הסדרה, שנראה בהמשך). כשהיא מוצגת כך, אפשר להבין למה מספרי קטלן הם כל כך בסיסיים - הנוסחה בעצם מתארת כל סיטואציה שבה כדי לבנות אובייקט מגודל \( n+1 \) אנחנו בונים זוג אובייקטים שהגודל שלהם מסתכם אל \( n \), וכל זוג כזה מייצר לנו באופן ייחודי אובייקט מגודל \( n+1 \). זה טיפה טריקי (לפחות עבורי) לראות את זה ישירות עבור שילוש של מצולעים בגלל שמצולע מ”גודל” \( n+1 \) במקרה הזה הוא מצולע עם \( n+3 \) קודקודים ובהתאם, כשאנחנו מפרקים אותו לאובייקט מגודל \( i \) ומגודל \( n-i \) יש לנו מצולעים עם \( i+2 \) קודקודים ו-\( n-i+2 \) קודקודים ולכן בסך הכל \( n+4 \) קודקודים שאחד מהם (קודקוד \( i \)) נספר פעמיים ולכן הם בדיוק \( n+3 \) הקודקודים של המצולע המקורי. הצלחתן לעקוב? יופי, כי אני לא. בכל פעם שבה אני מנסה לראות את זה ככה אני מסתבך בגלל כל עניין הפלוס 2 הזה; לכן הצגתי את זה קודם עם ה-\( T \)-ים.
למרבה המזל יש בעיות קומבינטוריות שנותנות את \( C_{n} \) בצורה ישירה יותר.
מסלולי שריג
גם כאן, תמונה אחת עוזרת מאוד להבין מה אני בכלל רוצה. ראשית, תמונה של כל ה-14 אובייקטים מגודל 4 שאני הולך לספור:
אוקיי, אולי זה לא לגמרי ברור. בואו נראה עוד דוגמא קונקרטית:
יש לנו כאן לוח משבצות, אבל אני מתעניין פחות במשבצות הפעם ויותר בקודקודים שלהן ובקווים שמחברים אותן - לרשת כזו של קודקודים וקווים במרווחים שווים קוראים שריג. עכשיו, אני נותן קואורדינטות לכל נקודות השריג כך ש-\( \left(0,0\right) \) היא הנקודה השמאלית-תחתונה ו-\( \left(7,7\right) \) היא הקואורדינטה הימנית-עליונה, ואני מסתכל על מסלול שמתחיל מ-\( \left(0,0\right) \) ומסתיים ב-\( \left(7,7\right) \). כל צעד במסלול עובר מקודקוד אחד לאחר על הקו שמחבר ביניהם, המסלול הספציפי שלי מתחיל בצעד ימינה, ואז למעלה, ימינה, למעלה… טוב, זה כאב ראש לתאר הכל במפורש, אבל אפשר לתאר בצורה קומפקטית בתור רצף של אותיות: R מסמן צעד ימינה ו-U מסמן צעד למעלה, ואז המסלול שמתואר באיור הוא
RURURRRUURUUUR
ספירה מהירה תראה שיש במסלול הזה 14 צעדים - בדיוק 7 צעדי R ו-7 צעדי U, מה שלא כל כך מפתיע כי כדי להגיע מלמטה למעלה צריך 7 צעדים, וכך גם כדי להגיע משמאל לימין. השאלה היא רק מה יהיה הסדר הפנימי בין הצעדים הללו. עכשיו, אפשר להוסיף גם צעדים שמאלה/למטה, אבל הם רק יובילו לכך שהמסלול יהיה ארוך יותר, ואנחנו מתעניינים בשאלה כמה מסלולים קצרים ביותר יש. באופן כללי, לכל \( n \) טבעי, אנחנו שואלים את השאלה כמה מסלולי שריג יש מ-\( \left(0,0\right) \) אל \( \left(n,n\right) \) שאורכם בדיוק \( 2n \).
מתברר שזו שאלה קלה שאנחנו לא צריכים את מספרי קטלן עבורה, אבל כן צריך להכיר קצת קומבינטוריקה בסיסית מהסוג שתיארתי בפוסט הזה: שם דיברתי על כך שמספר האפשרויות לבחור \( k \) מתוך \( n \) איברים, כשאין חשיבות לסדר שבו האיברים נבחרים ואי אפשר לבחור איבר פעמיים, הוא בדיוק מה שמסומן בתור \( {n \choose k} \) (קרי: “\( n \) בחר \( k \)”) ושווה ל-\( {n \choose k}=\frac{n!}{k!\left(n-k\right)!} \). אני אניח פה שהדבר הזה מוכר.
עכשיו, אפשר לחשוב על מסלול מאורך \( 2n \) שכולל בדיוק \( n \) צעדי U ו-\( n \) צעדי R בתור משהו שניתן להרכיב כך: ראשית, מבין \( 2n \) הצעדים במסלול (הצעד הראשון, השני, השלישי וכו’) אנחנו בוחרים בדיוק \( n \) ומציבים בהם U, ואז בכל השאר מציבים R. זו בחירה בלי חשיבות לסדר, כי זה לא משנה אם קודם החלטתי שבצעד 1 יהיה U ואז החלטתי שבצעד 5 יהיה גם U או אם החלטתי את זה קודם עבור צעד 5 ורק אז עבור צעד 1. זו גם בחירה שבה אי אפשר לבחור איבר פעמיים, כי אני לא יכול להחליט שאני רוצה לדחוף לצעד 5 “פעמיים U”. לכן מספר מסלולי השריג מאורך \( 2n \) מ-\( \left(0,0\right) \) אל \( \left(n,n\right) \) הוא בדיוק \( {2n \choose n} \). זה היה קל.
אז בואו נסבך קצת את הבעיה. אני הולך למתוח אלכסון בלוח שלי, ולחפש רק את המסלולים שלא מגיעים מעל האלכסון, כלומר לא מבקרים באף משבצת מהצורה \( \left(a,b\right) \) כך ש-\( a<b \). המסלול שציירתי קודם כמעט מקיים את זה, אבל נכשל ברגע האחרון:
כדי שיהיה קל להבין מה הולך פה, האיור שלי משתמש בויזואליזציה נחמדה שראיתי במקור בויקיפדיה האנגלית: צובעים את כל המשבצות מתחת למסלול בצבע כתום, והקריטריון לכך שהמסלול תקין הוא שהאלכסון (הקו המקווקו) לא עובר בתוך אף משבצת כתומה. כמה מסלולים כאלו יש? האינטואיציה הראשונית שלי היא שחצי ממספר המסלולים הכולל, כלומר \( \frac{1}{2}{2n \choose n} \), כי אנחנו לוקחים רק את המסלולים שמתחת לאלכסון ולכל מסלול כזה יש מסלול סימטרי מעל האלכסון (כזה שבו כל צעד “למעלה” מוחלף בצעד “ימינה” וכל צעד “ימינה” מוחלף בצעד “למעלה”). רק שכמובן שזה לא עובד כי רוב המסלולים הם בכלל כאלו שחוצים את האלכסון, לא שנשארים רק מעליו או מתחתיו. אז מה עושים?
אני אתחיל מלמצוא נוסחה רקורסיבית עבור מספר המסלולים, והפלא ופלא נקבל בדיוק את הנוסחה הרקורסיבית שכבר ראינו עבור \( C_{n} \). אחרי זה נראה להטוט שאני מאוד אוהב שיאפשר לנו לקבל עבור \( C_{n} \) את הנוסחה המדויקת \( C_{n}=\frac{1}{n+1}{2n \choose n} \). אם היקום היה מושלם, אז הלהטוט היה פשוט לראות בעיה קומבינטורית שקל באופן ישיר לראות שיש לה \( \frac{1}{n+1}{2n \choose n} \) פתרונות, אבל את זה אני לא יודע איך עושים אז אעשה משהו קצת יותר מתוסבך, אבל לא הרבה יותר.
אז איך נראה מסלול שריג “חוקי”, כזה שבשום שלב לא עובר מעל האלכסון? דבר אחד שאנחנו יודעים בודאות הוא שהצעד הראשון חייב להיות R, אחרת המסלול יגיע מעל האלכסון כבר בצעד הראשון שלו. אז בואו נתחיל את זה:
אחרי הצעד הזה, המסלול לא נוגע באלכסון - הוא מתחתיו. הדבר השני שאנחנו יודעים הוא שמתישהו המסלול הולך לגעת באלכסון - לכל המאוחר הוא יגיע אליו ממש בסוף, כשיגיע אל \( \left(n,n\right) \), אבל הוא בהחלט יכול להגיע לשם עוד קודם ולגעת בו כמה פעמים. מה שאני הולך להסתכל עליו הוא מה שקורה למסלול עד הפעם הראשונה שבה הוא מגיע אל האלכסון. מה שברור הוא שבצעד האחרון, שבו מגיעים אל האלכסון, המסלול הולך למעלה (כי אם הוא היה הולך ימינה ומגיע אל האלכסון, זה אומר שהוא נמצא מעליו, וזה לא חוקי). אז מה קורה למסלול בין ה-R ההתחלתי וה-U האחרון הזה? אפשר לצייר עוד אלכסון, מתחת לאלכסון המרכזי שלנו, לקרוא לו “האלכסון המשני” ולראות שהמסלול שלנו בין הצעד הראשון והאחרון נמצא כולו מתחת לאלכסון המשני. פשוט כי לעלות מעל האלכסון המשני אומר להגיע ולגעת באלכסון הראשי, וזה מה שאמרתי שקורה רק בסוף. במילים אחרות - בין הצעד הראשון והאחרון יש לנו עוד משהו שמתנהג בדיוק כמו מסלול שריג חוקי, פשוט על שריג קטן יותר. בדוגמא שלי צבעתי באדום את הצעדים שמתאימים למסלול הזה והאורך שלו הוא 6 (כלומר, 3 צעדי R ו-3 צעדי U).
אחרי ההגעה לאלכסון הראשי, יש לנו עוד מסלול שמתנהג כמו מסלול שריג חוקי שלא עובר מעל האלכסון, פשוט על שריג קטן יותר - המשבצות שנותרו. אצלי צבעתי אותו בכחול והאורך שלו הוא גם כן 3:
זו החוקיות הכללית: כל מסלול חוקי מאורך \( 2n \) מורכב מ-R בהתחלה (שמביא את המסלול אל \( \left(1,0\right) \)), ואז מסלול חוקי מאורך \( 2k \) כלשהו (שמביא את המסלול אל \( \left(k+1,k\right) \)), ואז U (שמביא את המסלול אל \( \left(k+1,k+1\right) \)) ואז עוד מסלול חוקי (שמגיע אל \( \left(n,n\right) \)). מכיוון שהאורך הכולל של המסלולים הוא \( 2n \) ו”בזבזנו” 2 צעדים על ה-R בהתחלה וה-U בהמשך ובזבזנו עוד \( 2k \) צעדים על המסלול החוקי הראשון, אז השני יהיה מאורך \( 2n-2-2k=2\left(n-k-1\right) \). כדי שהמספרים ייראו נחמד, בואו נדבר על מסלול מאורך \( 2\left(n+1\right) \), נמשיך לקרוא לאורך של המסלול הראשון \( 2k \) ואז האורך של השני יהיה \( 2\left(n-k\right) \).
קל לנחש את הצעד הבא: אני אסמן ב-\( C_{n} \) את מספר המסלולים מאורך \( 2n \), אז קיבלתי ש-
\( C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \)
מה שאנחנו רואים פה בפעולה הוא בדיוק את העיקרון של “שני אובייקטים בלתי תלויים שסכום הגדלים שלהם הוא \( n \) מצטרפים ליצירת אובייקט חדש מגודל \( n+1 \)” (כאן ה”גודל” הוא, נאמר, מספר צעדי ה-R). עבורי, כשאני סתם רואה את הנוסחה של קטלן, השאלה שבאה מעצמה היא “למה בעצם איברים שסכום הגדלים שלהם הוא \( n \) יוצרים משהו מגודל \( n+1 \)? מאיפה הפלוס אחד הזה בא?” וכאן אנחנו רואים דוגמא לדרך שבה הוא עשוי לבוא - אין לנו חופש בחירה מלא של איך לבנות את האובייקט החדש מתוך הקיימים; אנחנו חייבים לתת צעד ראשון R, מה ש”מבזבז” לנו צעד אחד.
אגב, מה מקרה הקיצון כאן? מה קורה בעצם כש-\( k=0 \)? במקרה הזה המסלול הראשון הוא “ריק” ולא כולל צעדים: המסלול הגדול פשוט עושה את ה-R בהתחלה ואז מייד את ה-U שמביא אותו אל האלכסון הראשי - וזה בסדר, אנחנו סופרים את המסלול הריק פעם אחת והנוסחה מסתדרת יפה (“מסלול ריק” זו לא איזו המצאה תלושה; זו בסך הכל סדרה ריקה, דהיינו פונקציה שהתחום שלה ריק, כלומר קבוצה ריקה - אפשר לפרמל את זה עד הסוף, אבל האם זה באמת עוזר לנו להבין את זה יותר טוב?)
טוב ויפה, אז שוכנענו שמספר מסלולי השריג שלא עולים מעל האלכסון הוא בדיוק מספר קטלן, אבל הבטחתי להראות דרך למצוא נוסחה סגורה עבורם בעזרת מסלולי שריג. בואו נראה את זה קורה. מה שאני הולך לעשות בפועל הוא לספור את המסלולים הלא חוקיים, אלו שכן חוצים את האלכסון. אני אוכיח שהמספר שלהם, עבור השריג מגודל \( n \), הוא \( {2n \choose n-1} \). עכשיו אפשר לעשות טיפה אלגברה:
\( {2n \choose n-1}=\frac{\left(2n\right)!}{\left(n-1\right)!\left(n+1\right)!}=\left(2n\right)!\cdot\frac{n}{n!}\cdot\frac{1}{n!\left(n+1\right)}=\frac{\left(2n\right)!}{n!n!}\cdot\frac{n}{n+1}={2n \choose n}\cdot\frac{n}{n+1} \)
מכיוון שמספר המסלולים הכללי הוא \( {2n \choose n} \), אני אקבל שמספר המסלולים החוקיים הוא:
\( {2n \choose n}-{2n \choose n-1}={2n \choose n}-{2n \choose n}\cdot\frac{n}{n+1} \)
\( ={2n \choose n}\left(1-\frac{n}{n+1}\right)=\frac{1}{n+1}{2n \choose n} \)
קיבלנו את הנוסחה הסגורה \( C_{n}=\frac{1}{n+1}{2n \choose n} \). יש כאמור עוד שלל דרכים להסיק אותה (ואוילר עשה את זה אלגברית, בעזרת הפונקציה היוצרת) אבל אני אוהב את הדרך הקומבינטורית שאראה עכשיו כי היא מאוד ציורית.
האתגר שלנו הוא לספור כמה מסלולים קיימים שכן עולים מעל האלכסון. בדומה למה שעשיתי קודם, גם עכשיו הרעיון יהיה להסתכל על מסלול כללי כזה ולפרק אותו לחלק שלפני המעבר על החוק, והחלק שאחריו, ואז לעשות איזו מניפולציה. בואו נראה דוגמא:
הפעם הראשונה שבה המסלול הזה מגיע אל מעל האלכסון המרכזי הוא בקואורדינטה \( \left(4,5\right) \). מה שקורה אז הוא שהמסלול נוגע לראשונה באלכסון המשני שנמצא מעל האלכסון הראשי - כלומר האלכסון \( y=x+1 \).
עכשיו מגיע הטריק: אני הולך לשקף את החלק של המסלול עד להגעה אל \( \left(4,5\right) \), ולשקף אותו ביחס לאלכסון המשני הזה. זה הולך להיראות ככה:
המסלול המשוקף עושה בדיוק ההפך ממה שהמסלול הרגיל עושה - בכל פעם שהרגיל עושה U המשוקף עושה R, ולהפך. הבדל נוסף הוא בנקודת ההתחלה: המסלול הרגיל מתחיל בנקודה \( \left(0,0\right) \), שהיא צעד R אחד מהנקודה \( \left(-1,0\right) \) שדרכה עובר האלכסון המשני; המסלול המשוקף מתחיל בנקודה שהיא צעד U אחד מאותה נקודה, כלומר הוא מתחיל מ-\( \left(-1,1\right) \).
עכשיו, אם ניקח את המסלול המשוקף עד שהוא מגיע לנקודה \( \left(4,5\right) \) ואז נמשיך ללכת במסלול הרגיל, מה שקיבלנו הוא מסלול מ-\( \left(-1,1\right) \) אל \( \left(10,10\right) \), והיופי הוא כמובן שזה עובד באופן כללי. כלומר, הטכניקה הזו של “לקחת מסלול שעובר מעל האלכסון הראשי, להעביר אלכסון משני מהנקודה הראשונה שבה זה קורה, לשקף ולחבר עם המשך המסלול” - זו טכניקה שבהינתן מסלול שעובר מעל האלכסון הראשי נותנת לנו מסלול מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \). לא קשה להוכיח את זה פורמלית: הרי מסלול הוא בסך הכל סדרה של U ו-R, ומה שעושה פעולת השיקוף היא כאמור להפוך כל R אל U וכל U אל R. אם אנחנו עושים את זה עבור מסלול כללי עד הנקודה שבה המסלול הגיע לנקודה מהצורה \( \left(a,a+1\right) \), זה אומר שהמסלול כלל \( a \) צעדי R ו-\( a+1 \) צעדי U ולכן המסלול המשוקף כולל \( a \) צעדי U ו-\( a+1 \) צעדי R - ולכן אם הוא מתחיל מ-\( \left(-1,1\right) \) הוא יגיע אל \( \left(-1+\left(a+1\right),1+a\right)=\left(a,a+1\right) \) ומשם אפשר יהיה להמשיך אותו כרגיל.
העניין הוא שאפשר לעשות גם את ההפך: לקחת מסלול כלשהו מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \) ולקבל ממנו מסלול מ-\( \left(0,0\right) \) אל \( \left(n,n\right) \) שעובר מעל האלכסון. הרעיון פשוט: ברגע שהמסלול שלנו נוגע באלכסון המשני \( y=x+1 \), לבצע עליו את אותה פעולת שיקוף בדיוק. והנה הפאנץ’: כל מסלול מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \) חייב מתישהו להגיע אל האלכסון המשני, כי הוא מתחיל את המסלול מעליו אבל מסיים את המסלול מתחתיו. מכאן שבאמת אפשר להפוך ככה כל מסלול מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \), ובמילים אחרות - ההתאמה בין מסלולים מ-מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \) ומסלולים לא חוקיים מ-\( \left(0,0\right) \) אל \( \left(n,n\right) \) היא התאמה חח”ׂע ועל - גודל שתי הקבוצות הללו זהה. אבל מסלולים כלשהם מ-\( \left(-1,1\right) \) אל \( \left(n,n\right) \) שכוללים רק צעדי U ו-R - את זה קל לספור. מסלול כזה חייב להכיל \( n+1 \) צעדי R ו-\( n-1 \) צעדי U, ולכן מספר הצעדים הכולל שלו הוא \( \left(n-1\right)+\left(n+1\right)=2n \) ומתוכם צריך לבחור \( n-1 \) כדי להציב בהם את ה-U - וזה בדיוק \( {2n \choose n-1} \). קיבלנו את התוצאה שחיפשנו.
למסלולי שריג יש שם: מסלולי דיק (Dyck), והם קשורים בצורה ישירה לסדרות של תווים שנקראות מילות דיק. הרעיון במילת דיק, בהקשר הזה, הוא שזו מילה מאורך \( 2n \) שמורכבת משני תווים שכל אחד מופיע \( n \) פעמים - אלו בדיוק ה-U,R אצלנו. הדרישה הנוספת, שתואמת את הדרישה שהמסלול לא יעבור מעל האלכסון, היא שבאף רישא של המילה לא יהיו יותר U מאשר R-ים (רישא היא תת-מילה שמקבלים מכך שמתחילים מהאות הראשונה במילה, מתקדמים הלאה ועוצרים מתישהו). דרך אחרת לתאר מסלולי דיק היא אם מפרשים את U בתור “למטה וימינה” ואת R בתור “למעלה וימינה” ואז מקבלים מסלול מ-\( \left(0,0\right) \) אל \( \left(n,0\right) \) שלא יורד מתחת לציר \( x \) בשום שלב. הנה ציור סכמטי של איך 14 המסלולים מאורך 4 נראים:
דרך נחמדה אחת לחשוב על מילות דיק היא אם מפרשים את R בתור סוגריים שמאליים, כלומר הסימן “)”, ואת U בתור סוגריים ימניים, כלומר “(“. כשכותבים סוגריים, מקובל לפעמים לשים סוגריים בתוך סוגריים (אמנם, לא תמיד אבל זה די נפוץ (למשל פראצ’ט מאוד אהב התחכמויות כאלו (האמת שאני לא בטוח אם פראצ’ט השתמש בסוגריים בתוך סוגריים או בהערות שוליים בתוך הערות שוליים) והוא לא היחיד מסוגו) ולכן כשאני משתמש בזה כאן זה לא כזה חריג). כשכותבים משמאל לימין, כמו למשל במתמטיקה, הכלל הוא שסוגריים שמאליים פותחים קונטקסט חדש וסוגריים ימניים סוגרים את הקונטקסט הפתוח הנוכחי. אם ברישא כלשהי יהיו יותר סוגריים ימניים משמאליים, זה אומר שייסגרו יותר קונטקסטים מאשר נפתחו עד כה, וזה לא הגיוני - ולכן זה “אסור”. ובאמת, כשמנסים לנתח ביטוי שכולל סוגריים הרבה פעמים עושים בדיוק את הפירוק שראינו כאן - הולכים עד הפעם הראשונה שבה מספר הסוגריים הימניים משתווה לשמאליים, ומפרקים ל”מה שבין הסוגר הימני שבהתחלה והסוגר השמאלי שעכשיו, וכל מה שבא אחר כך”.
עצים
נראה לי שכבר הבנו את הרעיון - אני מציג משהו חדש שמתאים למספרי קטלן, קודם כל אני מראה תמונה של 14 האובייקטים שמתאימים לגודל 4, כלומר למקרה \( C_{4}=14 \):
מה שאנחנו רואים פה הוא עצים בינאריים עם 4 צמתים. עצים בינאריים כאלו הם מקרה פרטי של גרף - הרעיון בגרף הוא שיש לנו אוסף של נקודות שנקראות “צמתים” וקווים שמחברים אותם, שנקראים “קשתות”. הרעיון הכללי ב”עץ” הוא שזה גרף שבו יש צומת מיוחד - “השורש” - שאפשר להגיע ממנו לכל הצמתים האחרים בגרף. אנחנו אוהבים לצייר עצים כך שהשורש הוא הצומת העליון ביותר וה”כיוון” של העץ הוא כלפי מטה (אבל אם רוצים אפשר גם להגדיר שמותר לעלות למעלה בחזרה, מה שאומר שכל צומת הוא בעצם שורש, וזו לא בעיה). אם אנחנו משתמשים בקונבנציה הזו של “מלמעלה למטה” אז בסיטואציה שבה יש קשת מצומת א’ לצומת ב’ הנמוך יותר, אומרים שא’ הוא אבא של ב’ ושב’ הוא ילד של א’. הרעיון בעץ בינארי הוא שלכל צומת יש לכל היותר שני בנים - ויותר מכך, יש ביניהם סדר. יש בן ימני ובן שמאלי, וזה נשאר כך גם אם אחד מהבנים חסר. כלומר, לכל צומת יש ארבע אפשרויות: או שיש לו שני בנים, או שאין לו בנים, או שיש לו בן ימני או שיש לו בן שמאלי.
עצים בינאריים הם מושג חשוב ומועיל במדעי המחשב - למשל, נוח לאחסן בהם נתונים בצורה שהופכת חיפושים ליעילים. אבל כאן אנחנו מתעניינים במספר שלהם, וכצפוי התוצאה היא שמספר העצים הבינאריים עם \( n \) צמתים הוא \( C_{n} \). גם פה קל לראות את זה בעזרת בניה רקורסיבית, ועצים הם אולי המקרה הטבעי ביותר שבו בניה כזו צצה; זה ממש נעוץ בהגדרה. אני מגדיר עץ בינארי באופן הבא: עץ ריק (עם 0 צמתים) הוא עץ בינארי, ובהינתן שני עצים בינאריים \( T_{1},T_{2} \) ניתן לבנות מהם עץ בינארי חדש על ידי הוספת צומת שורש חדש כך שאם יש ל-\( T_{1} \) שורש, הוא הבן הימני של השורש החדש, ואם יש ל-\( T_{2} \) שורש הוא הבן השמאלי של השורש החדש.
עם ההגדרה הזו, מה קיבלנו? שמשני עצים אנחנו מקבלים עץ חדש על ידי הוספת צומת. כלומר, אם קודם סכום הצמתים ב-\( T_{1},T_{2} \) היה \( n \), בעץ החדש יש \( n+1 \) צמתים. מכאן הנוסחה הרקורסיבית מגיעה מייד - והפעם הבניה הייתה סימטרית, להבדיל ממה שקרה עבור שילושים או מסלולי שריג.
יופי, זה היה פשוט! בואו נעבור למשהו קצת יותר מוזר:
מה אנחנו רואים כאן? גם זה נראה כמו עצים, אבל לא בינאריים - יש צמתים עם יותר משני בנים. אלו גם לא עצים עם 4 צמתים אלא דווקא עם 5 צמתים, אז מה הקטע? עצים כאלו נקראים “עצים סדורים” (או plane trees ועוד כל מני שמות) וההסבר הכי פשוט מה הם הוא פשוט ההגדרה: עץ סדור הוא גרף שכולל צומת מיוחד שנקרא השורש של העץ, ובנוסף יש רשימה \( P_{1},\ldots,P_{n} \) (אולי ריקה) של עצים סדורים כך שלכל \( i \) יש קשת מהשורש של העץ אל השורש של \( P_{i} \), והסדר בין הבנים של צומת הוא חשוב (כלומר, הרשימות \( P_{1},P_{2} \) ו-\( P_{2},P_{1} \) ייתנו עצים שונים אם \( P_{1}\ne P_{2} \)).
עבור עצים סדורים מתקיים שמספר העצים הסדורים עם \( n+1 \) צמתים הוא \( C_{n} \), וזה מה שמודגם באיור. במבט ראשון זה קצת מפתיע - עץ סדור זו הגדרה יותר “חופשית” מעצים בינאריים, אז איך ייתכן שיש יותר עצים בינארים מעצים סדורים? הרי בהינתן \( n \) יש \( C_{n} \) עצים בינאריים אבל רק \( C_{n-1} \) עצים סדורים עם \( n \) צמתים. העניין הוא שבעץ בינארי מקרים של בנים חסרים עדיין נספרים. כמו שאמרתי קודם, אנחנו מבדילים בין המקרה שבו יש לצומת רק בן ימני והמקרה שיש לו רק בן שמאלי - ואת זה אין בעצים סדורים. אם יש רק בן יחיד לצומת, אז זה מקרה אחד שלא הולך להיספר פעמיים.
טוב ויפה, אז איך מראים שעצים סדורים מקיימים את הנוסחה הרקורסיבית? ובכן… אה… אני לא יודע. עבורי זה מקרה מעניין בדיוק בגלל שעצים סדורים לא נראים ממבט ראשון כמו משהו שקל להתאים לבניה רקורסיבית של שני חלקים. אני מניח שאם מתאמצים קצת אפשר למצוא דרך לקבל את הנוסחה הרקורסיבית גם כאן, אבל אני לא רוצה לעשות את זה כי יש התאמה חד-חד-ערכית ועל יפהפיה בין עצים בינאריים ועצים סדורים. בואו נראה דוגמא לאיך זה עובד, באדיבות הספר של Stanely:
בצד שמאל יש לנו עץ סדור ובצד ימין יש לנו את העץ הבינארי שמתאים לו, כשבמרכז יש לנו איזה שהוא “ייצוג ביניים” שמסביר איך מקבלים אחד מהשני. איך זה עובד? נתחיל מהעץ הסדור בצד השמאל ונבצע עליו את הפעולות הבאות:
- לכל צומת, נחבר כל בן של הצומת לבן הבא בתור של הצומת בקו מקוווקו.
- לכל צומת, נמחק את כל הקשתות ממנו לבנים שלו חוץ מאשר לבן השמאלי ביותר.
- נמחק את צומת השורש מהגרף.
- נהפוך את הקווים המקווקווים לקווים רגילים.
במילים אחרות, כל צומת “איבד” את כל הבנים שלו חוץ מאחד, אבל “הרוויח” את אחד האחים שלו (אם יש כזה). הבנים של הצומת שנותקו לא הלכו לאיבוד כי כולם עדיין מחוברים אל הבן שלא נותק, והעץ בינארי כי עכשיו לכל צומת יש לכל היותר שני בנים: הבן השמאלי המקורי שלו (אם היו לו בנים) והאח שמימין לו (אם היה לו כזה).
למה זו התאמה חח”ע ועל? כי אפשר להפוך אותה, כלומר מכל עץ בינארי לקבל עץ סדור, ובצורה כזו שאם נתחיל מעץ סדור, נהפוך אותו לבינארי ואז חזרה לעץ סדור, אכן נחזור לעץ שהתחלנו ממנו. הנה השיטה:
- נוסיף לגרף צומת חדש שיהיה מחובר לבן שמאלי יחיד - השורש של הגרף המקורי.
- לכל צומת, אם יש לו בן ימני נהפוך את הקו שמחבר אותם למקווקו.
- לכל צומת \( a \), אם יש לו בן שמאלי \( b \), נלך ימינה על גבי הקווים המקווקווים החל מ-\( b \) ונהפוך כל צומת שנפגוש בדרך לבן של הצומת \( a \), כשהסדר שלהם הוא כמו הסדר שבו פוגשים אותם על המסלול (\( b \) נותר הבן הכי שמאלי).
- נמחק את הקווים המקווקווים מהגרף.
קל לראות שזה באמת עובד - ובחיי שזו התאמה מרהיבה.
דברים שלא נחתכים
בואו נראה עוד תמונה של 14 דברים!
מה שיש לנו כאן הוא קבוצות של 8 נקודות על מעגל. אני לא מצייר את המעגל כי הוא רק מקשה להבין מה קורה פה, אבל מכאן הנקודות מגיעות. חלק מהנקודות מחוברות בקווים שעוברים בתוך המעגל - מיתרים. הפואנטה פה היא שאנחנו מחלקים את הנקודות לזוגות, ובין כל זוג מעבירים מיתר, כך שהמיתרים לא נחתכים. עבור \( n \) מיתרים שאנחנו מעבירים דרך \( 2n \) נקודות נקבל \( C_{n} \) אפשרויות שונות לעשות את זה.
אם מנסים לפרמל את זה די מהר רואים דרך פשוטה לתאר סיטואציה של “היחתכות” בלי גאומטריה: אם אני אמספר את הנקודות על ידי \( 1,2,\ldots,2n \), אז המיתר \( \left(a,b\right) \) חותך את המיתר \( \left(c,d\right) \), כאשר אני מניח בלי הגבלת הכלליות ש-\( a<c \), רק אם \( c<b \) וגם \( d>b \). בניסוח שונה, אם אני אתאר את נקודות ההתחלה והסיום של אחד המיתרים עם סוגריים עגולים ושל מיתר אחר עם סוגריים מרובעים, אז הסיטואציה הבאה מובילה לחיתוך: \( )[(] \), וזאת להבדיל מ-\( \left(\right)\left[\right] \) שהיא בסדר (זה \( c>b \)) או \( \left(\left[\right]\right) \) שהיא גם בסדר (זה \( d<b \)).
כדי להוכיח שזה שקול למשהו שאנחנו כבר מכירים, בואו נעבור לייצוג ביניים שהוא בעיה מעניינת בפני עצמה:
כאן אנחנו מציירים \( 2n \) נקודות בשורה ומחברים אותן בקשתות שלא נחתכות. זה באופן מובהק אותו הדבר בדיוק כמו הנקודות על המעגל, אבל הציור שונה (ולשם שינוי קשה לי לסדר אותו בשתי שורות של שבע פריטים כל אחת, כי כל שורת נקודות כזו היא די ארוכה).
הרעיון הוא להתאים לכל סידור כזה מילת דיק, שאציג בתור סדרת סוגריים מאוזנת - כלומר, סדרה של אותו מספר של “)”{} ו-“(“ כך שבכל רישא אין יותר “(“ מאשר “)”. הנה איך זה עובד:
הרעיון פשוט: לכל נקודה, אם היא הראשונה בזוג שלה, שמים “)”{} ואם היא השניה שמים “(“, כשהולכים משמאל לימין. מכיוון שיש לנו חלוקה של \( 2n \) הנקודות ל-\( n \) זוגות יהיו לנו בסך הכל \( n \) מופעים של כל סוג סוגריים, אבל למה התנאי על הרישא מתקיים? זה די פשוט: בכל פעם שמופיע “(“ זה בגלל שהנקודה שמעליו היא השניה בזוג, כלומר בשלב מוקדם יותר פגשנו את הנקודה הראשונה שהתאימה לה ואז כתבנו “)”. לכן ההתאמה עובדת - אנחנו תמיד מקבלים מילת דיק חוקית.
כדי להשלים את ההתאמה צריך להסביר את הכיוון השני - איך בונים ממילת דיק התאמה כזו של נקודות לזוגות? גם זה קל: מעל כל אות במילת הדיק מציירים נקודה, ואז עוברים עליהן משמאל לימין. בכל פעם שבה נתקלים ב-“(“, מתחילים ללכת שמאלה שוב עד שמגיעים אל הנקודה הראשונה שטרם חוברה למישהו. היא בודאות תהיה מסומנת ב-“)”{} כי כאמור, בכל פעם שבה אנחנו נתקלים ב-“(“ אנחנו מייד מחברים את הנקודה שלו למישהו. התנאי על הרישות של מילות דיק מבטיח שתמיד נמצא מישהו להתחבר אליו, ומכיוון שאנחנו תמיד מתחברים לנקודה הפנויה הראשונה שאנחנו מגיעים אליה לא יכולים להיווצר חיתוכים.
כדי לראות את זה, בואו נחשוב שאני הנקודה \( b \) ואני מתחיל ללכת שמאלה כדי לחפש מישהו להתחבר אליו עד שאני מוצא \( a \) פנוי. עכשיו, האם ייתכן שיש נקודות \( c,d \) כך ש-\( a<c<b<d \)? לא! כי אם \( c \) מחוברת ל-\( d \) זה אומר שבזמן ש-\( d \) חיפש אל מי להתחבר, \( c \) הייתה פנויה, אבל אם זה היה המצב - למה \( b \) לא התחברה אליה אלא המשיכה עד \( a \)? אוקיי, אז \( a<c<b<d \) הוא בלתי אפשרי. מה בדבר \( c<a<d<b \)? במקרה הזה, מאותו שיקול, \( d \) לא הייתה יכולה להיות מחוברת אל \( c \) כי היא הייתה מתחברת אל \( a \) לפני כן. זה מסיים את ההוכחה.
מגדלי קפלר
שמרתי לסוף את הדבר הכי חדש והכי מוזר: מגדלי קפלר.
מה הולך כאן? כרגע זה בעיקר מזכיר לי את הסמל של ערוץ 1 העתיק, אבל חלק מהעניין הוא שבמקרה הזה, המגדלים מגודל 4 הם קטנים מדי מכדי שאפשר יהיה להסביר בצורה טובה את ההגדרה הכללית, אז אלך על דוגמא מורכבת יותר. המגדלים הוצגו במאמר Three Catalan Bijections של דונלד קנות’ שמספר שהם הומצאו בפברואר 2005 (חדשים!) על ידי Xavier Viennot שנתן להם את שמם. למה “קפלר”? קנות’ מסביר שזה בגלל שהדיאגרמה של מגדל קפלר (כמו אלו שרואים למעלה) מזכירה את מודל מערכת השמש של קפלר.
כדי לעזור להבין את הדוגמא הזו אני כבר אספר שאפשר לתאר מגדל קפלר בצורה פשוטה גם בתור רשימה של רשימות של רשימות של מספרים - פשוט! במקרה שלנו, המגדל הוא \( T=\left(W_{1},W_{2},W_{3}\right) \) כאשר \( W_{1}=\left[\left(1\right),\left(2\right),\left(3\right)\right] \) ו-\( W_{2}=\left[\left(1,3\right),\left(4\right),\left(1,3\right)\right] \) ו-\( W_{3}=\left[\left(1,3,5,7\right),\left(1,4,7\right),\left(3,8\right),\left(2,4,7\right),\left(1,7\right)\right] \).
עכשיו, כפי שאפשר לראות מהתמונה, מגדל קפלר מורכב מאוסף של מעגלים. כל מעגל כזה מכונה טבעת (Ring) ואפשר לראות שיש בכל טבעת קשתות שחורות בולטות. הקשתות הללו מכונות לבנים (Bricks) והן מה שאנחנו סופרים: יש בדיוק \( C_{n} \) מגדלי קפלר עם \( n \) לבנים.
עכשיו, אפשר גם לראות שהטבעות מאוגדות בקבוצות, עם רווחים גדולים שמסמנים מתי קבוצה אחת נגמרת והבאה בתור מתחילה. כל קבוצה כזו מכונה חומה (Wall). האינטואיציה הציורית שלנו יכולה להיות זו: חומה היא הדבר הרגיל שאנחנו חושבים עליו - אוסף של לבנים שמונחות בשכבות אחת מעל השניה. במקרה הזה השכבות הן מעגליות, וכל שכבה מכונה “טבעת” ומכילה כמה “לבנים”. קנות’ מציע לנו לחשוב על הלבנים כאילו הן עשויות מלגו, כך שאפשר “להדביק” לבנים זו לזו, כך שכדי שלבנה לא תיפול מספיק שתהיה מתחתיה לבנה במקום כלשהו, אפילו אם מרכז המסה שלה בולט החוצה.
בואו נעבור לדבר על זה קצת יותר פורמלי. בצורת הרישום \( T=\left(W_{1},W_{2},\ldots,W_{m}\right) \) כל \( W_{k} \) כזה הוא חומה, וכל חומה היא מהצורה \( W_{k}=\left(R_{1}^{k},R_{2}^{k},\ldots,R_{t_{k}}^{k}\right) \), כלומר כל חומה היא רשימה של טבעות, ובחומות שונות יכולים להיות מספרים שונים של טבעות. המוסכמה היא שאנחנו מתחילים מהמרכז ומתקדמים החוצה - כלומר, החומה הראשונה היא זו שהכי פנימית, והטבעת הראשונה בכל חומה היא זו שהכי פנימית וכן הלאה.
עכשיו, מה יש בכל טבעת? כאן העניינים מתחילים להסתבך. קונספטואלית, אנחנו מחלקים את המעגל לחלקים, וכל טבעת מכילה לבנים שהן חלק מהחלקים הללו. השאלה לכמה חלקים מחלקים את המעגל תלויה במספר החומה הנוכחי. בחומה הראשונה, כל המעגלים מחולקים ל-2 חלקים. בחומה השניה הם מחולקים ל-4 חלקים; בשלישית ל-8 וכן הלאה עם חזקות של 2. בניסוח פורמלי, \( R_{i}^{k}\subseteq\left[2^{k}\right] \), כאשר הסימון \( \left[n\right] \) הוא סימון סטנדרטי ל-\( \left\{ 1,2,3,\ldots,n\right\} \).
עכשיו, החוק שמגדיר את מגדלי קפלר קובע שבכל חומה, הטבעת הראשונה תמיד מכילה בדיוק את כל הלבנים האי-זוגיות, כלומר \( R_{1}^{k}=\left\{ 1,3,5,\ldots,2^{k}-1\right\} \). כל טבעת אחרת יכולה להכיל איזה מספרים שרוצים, אבל יש שתי מגבלות. כדי להבין איך הן נראות באופן ציורי, תעיפו לרגע מבט בציור - אפשר לראות שאני מצייר לבנים לא בתור בדיוק חצי עיגול, רבע עיגול וכו’ אלא קצת יותר מזה, כאילו הוספתי צ’ופצ’יקים בקצוות. זה אומר שאם היו לי שתי לבנים סמוכות באותה טבעת הן היו עולות אחת על השניה וזה אסור. זה גם אומר שאם יש לי בטבעת אחת לבנה במקום \( x \) ובטבעת שלפניה לבנה במקום \( x+1 \) או \( x-1 \), זה נראה שהן עולות אחת על השניה. אז הנה החוקים:
- אסור שבאותה טבעת יהיו שתי לבנים שעולות זו על זו. כלומר, אם \( x\in R_{i}^{k} \) אז \( x-1,x+1\notin R_{i}^{k} \), כאשר פעולות החשבון הן מודולו \( 2^{k} \).
- אם בטבעת שאיננה הראשונה בחומה יש לבנה כלשהי, היא חייבת להישען על לבנה בטבעת שלפניה. כלומר, אם \( x\in R_{i+1}^{k} \) \( x\in R_{i}^{k} \) או \( x-1\in R_{i}^{k} \) או \( x+1\in R_{i}^{k} \) כששוב, החשבון הוא מודולו \( 2^{k} \).
זהו, זו כל ההגדרה! טיפה מסובך, אבל אין קושי עקרוני לכתוב קוד שבודק אם רשימה של רשימות של רשימות של מספרים הוא מגדל קפלר חוקי, או קוד שיודע לייצר את כל המגדלים עם \( n \) לבנים (בצורה לא יעילה) וכדומה.
מה שקנות’ עושה במאמר שלו הוא להראות התאמה חח”ע ועל מפורשת בין מגדלי קפלר עם \( n \) לבנים ומסלולי דיק מאורך \( 2n \), ואני רוצה להציג את זה כאן, אם כי בצורה טיפה שונה ממה שקנות’ עושה. פישוט אחד שהוא לא קריטי אבל בהחלט יעזור לקוד שאני אציג להיות קצת פחות מסורבל הוא לשנות את איך שממספרים לבנים: במקום שהלבנים בקיר ה-\( k \) יהיו \( \left\{ 1,2,3,\ldots,2^{k}\right\} \) אני אסמן אותן ב-\( \left\{ 0,1,2,3,\ldots,2^{k}-1\right\} \). זה נוח, כי כשלוקחים דברים מודולו \( 2^{k} \) מקבלים מספרים בקבוצה הזו; אם היינו מסתכלים על הקבוצה מ-\( 1 \) עד \( 2^{k} \) היינו צריכים טיפה לשנות את איך שעושים מודולו, וזה סתם מסרבל.
הרעיון המבריק של קנות’ הולך ככה: אנחנו מסתכלים על מסלול דיק מאורך \( 2n \). אפשר לחשוב על מסלול כזה בתור סדרה של U ו-D כך ש-U הוא צעד למעלה-ימינה ו-D הוא צעד למטה-ימינה, והמסלול מתחיל בגובה 0, מסיים בגובה 0 ולא יורד מתחת לגובה 0 בשום שלב. הרעיון של קנות’ הוא עכשיו לשים “גבולות” - בגובה 1, בגובה 3, בגובה 7 וכן הלאה - בגובה \( 2^{k}-1 \) לכל \( k\ge0 \). כעת, חומה מספר \( k \) תיבנה על פי בסיס החלק של המסלול שמתחיל עם ההגעה הראשונה לגבול \( 2^{k}-1 \) ומסתיים עם ההגעה הראשונה לגבול \( 2^{k+1}-1 \), או מסתיים בסוף המסלול אם לא מגיעים לגובה הזה.
בואו נראה דוגמא:
מה שיש כאן הוא המסלול שמתאים למחרוזת הבאה:
UUDUDUDDUUUDUDDUUDDDUDUDUUUUUDUUUDDDUDDDUUDUUDDDDD
צבעתי את המסלול בשלושה צבעים - החלק הראשון בכחול, השני בירוק והשלישי באדום. הרעיון הוא שנשתמש בכל המסלול כדי לבנות מגדל קפלר: החומה הראשונה תיבנה על בסיס החלק הכחול, החומה השניה על בסיס החלק הירוק והשלישית על בסיס החלק האדום. מתי חלק מתחיל? החל מהפעם הראשונה שבה המסלול מגיע לקו הגבול שלו, ומרגע זה והלאה המסלול הקודם נזנח לאנחות. אפשר לראות שבאיור, הצעד הראשון צבוע בשחור - זה בגלל שעדיין לא הגענו אפילו לקו הגבול הראשון ולכן עוד לא התחלנו לבנות את החומות (אבל הצעד הראשון הוא תמיד למעלה ולכן תמיד נתחיל לבנות את החומה הראשונה מייד אחריו).
הרעיון עכשיו הוא זה: בחומה מס’ \( k \) יכולות להופיע לבנים שממוספרות ב-\( 0,1,\ldots,2^{k}-1 \), כלומר, מספרים שהם החל מ-0 וכלה בגובה של הגבול שהגעה אליו התחילה את המסלול שלנו. כפי שרואים טוב עם המסלול הירוק, המסלול יכול להיות מעל הגבול, וגם מתחת לגבול. בשני המקרים הללו העקרון הוא - אם המסלול ביצע צעד לכיוון הגבול, אז הצעד הזה יתורגם להוספת לבנה לחומה; אחרת הוא לא ישפיע על המגדל שאותו בונים. כך למשל במסלול הירוק, הצעד הראשון הוא למטה והוא מתרחק מהגבול, ולכן הצעד הזה לא יוסיף לבנה למגדל; אבל הצד השני הוא למעלה ומתקרב אל הגבול (ואפילו מגיע אליו) ולכן הוא כן יוסיף לבנה למגדל.
איזו לבנה הולכים להוסיף? זה תלוי בגובה של המקום שהגענו אליו אחרי הצעד. אם היינו מתחת לגבול וביצענו צעד למעלה, אז נוסיף את הלבנה שהמספר שלה הוא כמו הגובה של המסלול. אם היינו מעל הגבול וביצענו צעד אחד למטה, אז נוסיף את הלבנה שהמספר שלה הוא כמו הגובה של המסלול מעל הגבול, כלומר אם הגבול הוא 3 ואנחנו בגובה 5, אז נוסיף את לבנה 2. ככה זה נראה בדוגמא שלנו:
למשל, ה-0-ים בהתחלה מגיעים מכך שהקו הכחול שוב ושוב יורד אל הגבול. אחר כך הוא חוצה אותו כלפי מטה ואז עולה שוב - ולכן הפעם זה נספר בתור הגעה לגובה 1. או למשל, בחלק של הירוק שבו הוא מתחיל לעלות ולעלות הוא בהתחלה מוסיף את הלבנים 1,2,3 ואז פתאום מפסיק למרות שהעלייה נמשכת - למה? כי הוא חצה את קו הגבול 3, ומרגע שהוא חוצה אותו, לבנים חדשות מתווספות כשהוא יורד, לא כשהוא עולה.
מה בעצם הרעיון כאן? תסתכלו על המסלול הכחול: אסור לו לרדת מתחת ל-0 (כי כל מסלול דיק מקיים את זה) ו”אסור” לו להגיע אל 3 (כי בפעם הראשונה שבה הוא יגיע אל 3 הוא יהפוך להיות מסלול שונה, המסלול הירוק), כך שכל “מרחב התמרון” שלו הוא פס צר סביב קו הגבול 1: הוא יכול להיות ב-0,1,2 ולכן הלבנים שהוא יכול להוסיף מתחת לגבול הן 0 ו-1 (הגבהים האפשריים שלו מתחת לגבול, עד שמגיעים אליו) והלבנים שהוא יכול להוסיף מעל לגבול הן גם כן 0,1 (הגבהים שלו מעל הגבול הזה). כלומר, “מרחב התמרון” של המסלול הכחול מאפשר לו רק להוסיף לבנים עם המספר 0,1 ואלו בדיוק הלבנים שיכולות להופיע בחומה הראשונה במגדל.
המסלול השני, הירוק, מקבל מרחב תמרון רחב יותר ויכול להוסיף את הלבנים \( 0,1,2,3 \) שהן בדיוק מה שיכול להופיע בחומה השניה במגדל, וכן הלאה.
עכשיו, אפשר לשאול - בשביל מה זה טוב, שיש גם חלק מעל וגם חלק מתחת לקו הגבול, אם הם מייצרים את אותן לבנים בדיוק? ובכן, זה כל היופי פה: זה מאפשר למסלול ליצור לבנים כשהוא רוצה. תראו למשל את הסיום של המסלול האדום - הוא חייב לסיים בכך שהוא יורד עד 0, אבל מרגע שהוא מתחת לקו הגבול, עוד ירידה לא תוסיף לבנים - אז הצורך לרדת עד הסוף לא מכריח את המסלול להוסיף לבנים למגדל שהוא בונה. זה נותן לנו בדיוק את הגמישות שאנחנו צריכים כאן.
אם כן, טוב ויפה, אבל מה זה בעצם אומר, “להוסיף לבנה”? איך בוחרים לאיזו טבעת להוסיף אותה? ובכן, זה קל: פשוט זורקים אותה ורואים מה קורה.
בואו ניזכר איך חומה בנויה. ברגע שמתחילים חומה חדשה, כי המסלול הגיע לגובה מתאים חדש ושינה צבע, אוטומטית יוצרים חומה חדשה עם טבעת ראשונה שכוללת את כל המספרים שהטבעת הראשונה חייבת לכלול. כלומר, כשמגיעים לראשונה לגובה \( 2^{k}-1 \) יוצרים חומה חדשה עם הטבעת \( \left\{ 0,2,4,\ldots,2^{k}-2\right\} \). זה עדיין לא החלק של “להוסיף לבנים למגדל”, זה פשוט יוצר לנו את החומה הבסיסית שהמסלול יבנה מעליה.
עכשיו, אם המסלול רוצה להוסיף את הלבנה \( s \) למגדל, אנחנו עוברים על הטבעות במגדל מהעליונה ביותר אל התחתונה. לכל טבעת כזו, אם \( s \) או \( s+1 \) או \( s-1 \) (מודולו \( 2^{k} \)) נמצאות בה - “נתקענו” - אי אפשר להכניס את הלבנה לטבעת הזו (היא תתנגש באחת מהלבנים הללו) וגם אי אפשר לדחוף אותה דרכן אל טבעת נמוכה יותר כי הן חוסמות את הדרך (זו הצורה שבה כדאי לחשוב על זה כי זה נותן אינטואיציה למה הוספת לבנה מתנהגת כפי שהיא מתנהגת; הסיבה האמיתית להתנהגות הזו היא כי ככה הבניה עובדת). אם אף אחת מהלבנים הללו לא נמצאת בטבעת, אפשר לעבור לטבעת הבאה בתור, הנמוכה יותר, ולראות אם גם שם אפשר להתקדם או שנתקעים. בסופו של דבר מוסיף את הלבנה החדשה לטבעת הנמוכה ביותר שמצאנו שאפשר להוסיף את \( s \) אליה - או, אם לא הייתה כזו, פותחים טבעת חדשה שכוללת רק את \( s \).
זהו, זו כל הבניה! הנה קוד פייתון שעושה את הכל ואני מקווה שברור וחף מבאגים:
def add_brick(wall, s, n):
m = len(wall) - 1
while not (s in wall[m] or (s+1) % n in wall[m] or (s-1) % n in wall[m]):
m -= 1
if m == len(wall) - 1: # new ring
wall.append([])
wall[m+1].append(s)
def generate_kepler_tower_from_dyck(word):
tower = []
height = 0
for ch in word:
k = len(tower)
current_border = 2**k-1
next_border = 2**(k+1)-1
height += 1 if ch == 'U' else -1
if height >= current_border and ch == 'D':
add_brick(tower[-1], height - current_border, 2**k)
if height <= current_border and ch == 'U':
add_brick(tower[-1], height, 2**k)
if height == next_border:
new_wall = [[2*i for i in range(2**k)]]
tower.append(new_wall)
return towerהשאלה הראשונה שאנחנו צריכים לשאול את עצמנו היא אם הבניה הזו באמת נותנת מגדל קפלר, אבל ברור שהיא עושה את זה כי כללי הוספת הלבנים שלנו מבטיחים שתמיד יהיה לנו מגדל חוקי - אנחנו מוסיף במפורש את הטבעת הראשונה בכל חומה, וכשאנחנו מוסיפים לבנה אנחנו מקפידים שהיא תיכנס למקום שבו מותר לה להיות, ובטבעת שמתחתיה היא כבר לא יכולה להיכנס כי יש שם לבנה שעליה היא יכולה להישען.
שאלה קצת יותר טריקית היא למה מסלול מאורך \( 2n \) נותן מגדל קפלר עם בדיוק \( n \) לבנים. בדוגמא שראינו למעלה, המסלול שלי היה מאורך 50, כלומר \( n=25 \). אם סופרים את הלבנים שהמסלולים מוסיפים (המספרים שמתחת למסלולים, באיור השני) מגיעים ל-18. איפה הלבנים החסרות? ובכן, בטבעת הראשונה בכל חומה. יש לנו שלוש חומות. בחומה הראשונה הטבעת הראשונה היא \( \left\{ 0\right\} \), בשניה היא \( \left\{ 0,2\right\} \) ובשלישית היא \( \left\{ 0,2,4,6\right\} \). בסך הכל קיבלנו את שבע הלבנים החסרות - אבל איך בדיוק אנחנו יודעים שזה לא הסתדר בפוקס?
בואו נדמיין לרגע שהמסלול שלנו כולו מאותו צבע. במסלול הזה, בכל פעם שאנחנו מבצעים צעד “למעלה”, יהיה אי שם בהמשך צעד “למטה” שיקזז אותו, כי בסוף אנחנו חוזרים אל 0. אני אחדד: אם היה לנו צעד “למעלה” שהעלה אותנו מגובה \( h \) אל גובה \( h+1 \), יהיה צעד “למטה” שיוריד אותנו מגובה \( h+1 \) אל גובה \( h \). עכשיו, אם הצעדים הללו התבצעו מתחת לגבול אז צעד ה”למעלה” הוסיף לבנה וצעד ה”למטה” לא הוסיף; ואם הם התבצעו מעל לגבול אז צעד ה”למטה” הוסיף וצעד ה”למעלה” לא הוסיף. בשני המקרים בדיוק חצי מהצעדים שלנו הוסיפו לבנה.
אם נסתכל על האיור שבדוגמא, קל להיזכר שיש חריג - הצעד הראשון, שהוא צעד “למעלה” אל הגבול אבל הוא לא מוסיף לבנה, כי בשלב הזה המסלול הכחול עוד לא קיים. זה מתקזז עם העובדה שכשהגענו לגבול, יצרנו חומה חדשה עם טבעת ראשונה \( \left\{ 0\right\} \). זה גם מה שהולך לקרות באופן כללי כשיש לנו מסלול שמשנה צבע: כשהמסלול הירוק הגיע לגובה 7 ושינה את הצבע שלו, מה שקרה הוא שנוצרו אצלו צעדים שקודם לא הוסיפו לבנים אבל עכשיו יתקזזו עם עוד צעדים שלא יוסיפו לבנים: הצעדים החל מהגבול ומעלה, כלומר \( 3\to4\to5\to6\to7 \). ארבעה צעדים שעכשיו כשיתבצעו בכיוון ההפוך גם כן לא יוסיפו לבנים - אבל עכשיו מתקזזים עם העובדה שהמסלול האדום נפתח עם הוספת הטבעת \( \left\{ 0,2,4,6\right\} \).
זה קורה גם באופן כללי: אם היה לנו מסלול סביב קו הגבול \( 2^{k}-1 \) והוא הגיע אל \( 2^{k+1}-1 \) אז “איבדנו” את כל הצעדים \( 2^{k}-1\to2^{k}\to\ldots\to2^{k+1}-1 \), כלומר \( 2^{k} \) צעדים; אבל אז אנחנו יוצרים קיר חדש שבטבעת הראשונה שלו יש את \( \left\{ 0,2,\ldots,2^{k+1}-2\right\} \), כלומר בדיוק \( 2^{k} \) הלבנים שהיו חסרות לנו.
זה מוכיח שקיבלנו פונקציה ממסלולי דיק מאורך \( 2n \) אל מגדלי קפלר מגודל \( n \). כדי להראות שהיא חח”ע ועל, צריך להסביר איך להפוך אותה.
הרעיון הוא די פשוט: בהינתן מגדל קפלר, נבנה את המסלול שיוצר אותו “מהסוף להתחלה”, על ידי כך שנפרק לאט ובזהירות את החומות של המגדל. אם נעקוב אחרי הגובה הנוכחי של המסלול, נוכל לראות שבהינתן הגובה הזה והמצב הנוכחי של המגדל, יש בדיוק אפשרות אחת למצב של המגדל והגובה של המסלול בצעד הקודם שהביאו אותנו לכאן.
בואו נחזור למסלול שראינו קודם. כשמייצרים ממנו מגדל קפלר, מקבלים את זה:
אנחנו רוצים להבין איך אפשר לקבל ממנו בחזרה את המסלול הזה:
כאמור - אני ארכיב את המסלול מהסוף להתחלה. בשביל זה צריך לדעת בכל רגע נתון מה קו הגבול הנוכחי, שקובע איזו לבנה מוסיפים למגדל. עבור המסלול האדום קו הגבול הזה הוא ב-7. איך אפשר לדעת את זה רק מהסתכלות על מגדל הקפלר שלנו? אנחנו סופרים כמה חומות יש בו - כאן יש שלוש, מה שאומר שהחומה החיצונית ביותר, זו שאנחנו מתחילים מלפרק אותה, זו שתיתן את המסלול האדום - מורכבת מהלבנים \( \left\{ 0,1,2,\ldots,2^{3}-1\right\} \).
עכשיו, אנחנו זוכרים בכל רגע נתון מה הגובה הנוכחי של המסלול שאנחנו משחזרים מהסוף להתחלה, ומה המצב הנוכחי של המגדל (שאמור להיות תואם את המצב של המגדל כשהוא נבנה על ידי המסלול המקורי עד שהוא מגיע בדיוק אל הנקודה בשחזור שבה אנחנו נמצאים). אנחנו מתחילים מגובה 0. אם אני בגובה 0, מה היה הצעד הקודם? זה היה חייב להיות צעד D כי אם זה היה צעד U, והצעד הזה הביא אותי לגובה 0, זה אומר שקודם הייתי בגובה \( -1 \) וזה בלתי אפשרי. באופן דומה, אם במהלך הבניה של המסלול האדום הייתי איכשהו מטפס עד לגובה 14, הייתי יודע שהצעד הקודם היה חייב להיות U, כי צעד D היה אומר שקודם הייתי בגובה 15 וזה היה יוצר מסלול חדש, עם חומה חדשה - יותר חומות מאשר יש במגדל. אז אלו שני מקרי הקיצון שבהם אנחנו יודעים בדיוק מה חייב לקרות אפילו בלי לבדוק מה הולך עם הלבנים שבתוך המגדל שלנו - ובשני המקרים הללו, הצעדים שעושים הם לכיוון קו הגבול שבאמצע ולכן לא מוסיפים לבנים, ולכן אין לי מה להסיר לבנים מהמגדל שאני מפרק.
יש עוד אפשרויות. אם אני בגובה \( s \) שהוא 1 לפחות אבל עדיין מתחת לקו האמצע, יכלתי להגיע לגובה הזו או בפעולת D שלא הייתה מוסיפה לבנה למגדל, או בפעולת U שכן הייתה מוסיפה - והיא הייתה מוסיפה בדיוק את הלבנה \( s \), כי זה מה שקורה כשאנחנו מתחת לקו האמצע, אנחנו מוסיפים לבנה ששווה לגובה שהגענו אליו אחרי ביצוע הצעד. אז אנחנו מנסים להסיר מהמגדל שלנו את הלבנה \( s \), כלומר בודקים אם היא נמצאת בחומה הנוכחית, במיקום שבו אין לבנים אחרות שיושבות עליה, באחת מהטבעות מעל הטבעת הראשונה (הטבעת הראשונה כזכור נבנית בצורה שונה). אם היא שם, אנחנו מסירים אותה ומסמנים שבוצע צעד U, ואחרת פשוט מסמנים שבוצע צעד D, ומעדכנים את הגובה שלנו בהתאם (אם בוצע צעד U אנחנו מקטינים את הגובה, כי הרי אנחנו רוצים לדעת באיזה גובה היינו קודם). באופן דומה מטפלים גם במקרה שבו אנחנו מעל קו האמצע.
המקרה הכי בעייתי הוא זה שהוא אנחנו נמצאים בדיוק על קו האמצע. במקרה הזה יש שתי אפשרויות שונות להגעה לשם, ששתיהן מוסיפות לבנה למגדל - או עלייה למעלה שמוסיפה את הלבנה \( 2^{k}-1 \), או ירידה למטה שמוסיפה את הלבנה 0. אז מנסים לחלץ מהמגדל את שתי הלבנים הללו ורואים איזו מהן הצליחה. ברור שרק אחת היא אפשרית, כי שתי הלבנים הללו הן שכנות ולכן מתנגשות אחת עם השניה ולא יכולות להיות באותה טבעת, ולכן אם הן נמצאות במגדל, אחת נמצאת גבוה יותר והיא זו שתקבע לנו איזה מהלך אנחנו משחזרים. אבל למה בעצם שאחת משתיהן תהיה במגדל? אי אפשר להנדס מגדלים שבהם זה לא קורה? זה הטיעון הכי עדין כאן: אפשר להראות שאלא אם החומה התרוקנה למעט הטבעת הראשונה, זה לא יכול לקרות כי בדרך אל קו האמצע הזה היינו מרוקנים מהחומה כל לבנה שלא תקועה - חוץ מאשר הלבנים \( 0,2^{k-1} \) שאפשר להוציא רק כשמגיעים לאמצע, וכל לבנה אחרת שאי אפשר להוציא כי אחת משתי הלבנים הללו חוסמת אותה. זה טיעון קצת מעצבן להוכחה פורמלית אבל הוא עובד; כל מה שנשאר לעשות הוא לדבר על מה שקורה כשמגיעים לאמצע כשהחומה ריקה חוץ מהטבעת הראשונה, וברור מה עושים בשלב הזה - מעיפים את החומה ומתחילים לשחזר את המסלול מהצבע הבא (כלומר, הקודם).
הנה קוד (חף מבאגים, אני מקווה - היו בו כל כך הרבה בהתחלה!) שעושה את זה:
def remove_brick(wall, s, n):
# we are trying to understand if it's possible that s was the latest brick added to the tower
# for this, it's not enough that it's IN the tower, the way for it must be clear, meaning no s+1 and no s-1 in the way
# print(f"Trying to remove brick {s} from wall {wall}, num_segments={num_segments}")
for ring in reversed(wall[1:]): # skip the first ring, it's not touched by add_brick()
if s in ring:
ring.remove(s)
if len(ring) == 0: # if the ring is empty, remove it
wall.remove(ring)
return True
else:
if (s+1) % n in ring or (s-1) % n in ring:
return False
return False
def generate_dyck_from_kepler(tower):
tower = copy.deepcopy(tower) # we're going to remove bricks
word = []
height = 0
for k in range(len(tower)-1, -1, -1): # go over the walls from last to first
wall = tower[k]
current_border = 2**(k+1)-1
while len(wall) > 1 or height != current_border: # continue until wall is empty except the first ring
if height == 2*current_border:
# we're near the next border. we can't reach it, otherwise the tower would have had more walls
word.append('U')
height -= 1
elif height == 0:
# we're at the bottom, we can't go down anymore
word.append('D')
height += 1
elif height > current_border: # if s_down is in the tower, we made a "down" move, else nothing
if remove_brick(wall, height - current_border, 2**(k+1)):
word.append('D')
height += 1
else:
word.append('U')
height -= 1
elif height < current_border: # if s_up is in the tower, we made an "up" move, else nothing
if remove_brick(wall, height, 2**(k+1)):
word.append('U')
height -= 1
else:
word.append('D')
height += 1
elif height == current_border:
# we reached the border either by "down" from above, and then s_down is in the tower, or by "up" from below, and then s_up is in the tower
# they can't both be in the tower since in this case, s_down = 1 and s_up = current_border + 1, which are adjacent (modulo current_border + 1)
# print("height == current_border, so we are at the border, trying to remove bricks", s_down, s_up)
if remove_brick(wall, height - current_border, 2**(k+1)):
word.append('D')
height += 1
elif remove_brick(wall, height, 2**(k+1)):
word.append('U')
height -= 1
else:
raise ValueError("This should not happen")
word.append('U') # first step is always U
return ''.join(reversed(word))זה מסיים את הסיפור מבחינתי, אבל מספרי קטלן לא נגמרים שם - הספר של Stanely עמוס בשלל דוגמאות אחרות (אם כי חייבים להודות שרובן הן פשוט וריאציות עם כל מני מגבלות ופרמטרים על אותה בעיה), אבל שולי הפוסט הזה כבר צרים מלהכילן.
נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:
