כמה חלוקות יש, ואיך זה קשור לאוילר ולמספרים מחומשים?

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

אני רוצה לדבר הפעם על מה שלטעמי היא הבעיה היפה והמעניינת ביותר בקומבינטוריקה בסיסית - בעיית הספירה של חלוקות של מספרים טבעיים. מה זו חלוקה של מספר \( n \)? זו דרך לכתוב את \( n \) כסכום של מספרים טבעיים חיוביים, כשאין חשיבות לסדר של המחוברים. למשל, \( 3=1+2 \) היא חלוקה של \( 3 \), והיא זהה ל-\( 2+1 \). עוד חלוקות אפשריות של 3 הן פשוט 3 עצמה, ו-\( 1+1+1 \). אם כן, ל-3 יש \( 3 \) חלוקות. קל לראות של-1 יש חלוקה אחת, ול-2 יש שתי חלוקות. האם ל-4 יהיו, אם כן, 4 חלוקות? ובכן, לא, יש 5:

1. 4
2. \( 1+3 \)
3. \( 2+2 \)
4. \( 1+1+2 \)
5. \( 1+1+1+1 \)

אפשר להגדיר כך פונקציה: \( p\left(n\right) \) היא מספר החלוקות של המספר הטבעי \( n \) (ל-0 יש חלוקה יחידה, “ריקה”). הסדרה \( p\left(0\right),p\left(1\right),p\left(2\right),\dots \) מתחילה כך:

\( 1,1,2,3,5,7,11,15,22,30,42,56,77,\dots \)

ונשאלת השאלה - האם יש דרך חישוב פשוטה עבור \( p\left(n\right) \)?

כדי לראות מה זו “דרך חישוב פשוטה”, בואו נסתכל לרגע על בעיה דומה: יש לנו \( n \) כדורים שנמצאים ב-\( k \) תאים הממוספרים ב-\( 1,2,\dots,k \), (כשאפשר תאים ריקים ואפשר יותר מכדור אחד בתא). כמה סיטואציות אפשריות כאלו יש? ובכן, זה מה שנקרא בקומבינטוריקה בחירה עם החזרה וללא חשיבות לסדר: בחירה - לכל כדור בוחרים תא; עם החזרה - אפשר לבחור את אותו תא יותר מפעם אחת; ללא חשיבות לסדר - מה שמתעניינים בו הוא רק כמה כדורים יש בכל תא בסוף התהליך, לא כמה תהליכי חלוקה קיימים. יש לי פוסט שבו אני פותר את הבעיה הזו, והפתרון (שלא חשוב לפוסט הזה) הוא מה שמסומן ב-\( {n+k-1 \choose k} \) והוא סימון מקוצר ל-\( \frac{\left(n+k-1\right)!}{k!\left(n-1\right)!} \). זו נוסחה סגורה פשוטה שאפשר לחשב ממנה ערכים מספריים בקלות רבה יחסית.

אם ננסה לעשות ניתוח דומה עבור פונקציית החלוקה, מהר מאוד ניתקל בקשיים ונראה שהבעיה הזו חמקמקה הרבה משנראה במבט ראשון. עיקר הקושי הוא שקל לבצע בטעות ספירה כפולה כשמנסים לעשות הפרדה למקרים. הנה דוגמא עבור ניתוח שגוי של מספר החלוקות של 4: אני אומר, בואו ניקח מספר \( 1\le n\le4 \), ניקח את \( 4-n \) ונחשב את כל החלוקות שלו, נוסיף לכל אחת מהן את \( n \) והופס - קיבלנו חלוקה של 4 ואפשר להוסיף אותה לספירה. כל מה שנשאר לעשות הוא לעבור על כל הערכים האפשריים של \( n \).

במילים אחרות, אני מציע לבצע את החישוב הבא: \( p\left(4\right)=p\left(3\right)+p\left(2\right)+p\left(1\right)+p\left(0\right)=3+2+1+1=7 \). קיבלתי תוצאה גדולה מדי - ספרתי שתי חלוקות פעמיים. את מי? ובכן, אם \( n=2 \) אז אני בונה את החלוקה \( 2+\left(1+1\right) \) (החלק בסוגריים הוא חלוקה של \( 2=4-n \) במקרה הזה). אם לעומת זאת \( n=1 \) אז אני בונה את החלוקה \( 1+\left(2+1\right) \) (כאן הסוגריים הם חלוקה של \( 3=4-n \)). שתי החלוקות הללו הן אותו דבר. הסדר של האיברים בסכום שונה, אבל אמרנו שזה לא משנה לנו, ומכאן הספירה הכפולה.

אם השיטה שלי הייתה עובדת והיינו מקבלים ש-\( p\left(n\right) \) שווה לסכום כל ה-\( p\left(k\right) \)-ים עבור \( k<n \), האם הייתם מסכימים שזו דרך חישוב פשוטה? מצד אחד, זה אומר שכדי לחשב את \( p\left(n\right) \) צריך לחשב את כל האיברים שלפניו בסדרה; מצד שני, החישוב עצמו הוא מאוד פשוט. חשבו לרגע על סדרת פיבונאצ’י שמוגדרת באמצעות הכלל \( F\left(0\right)=0,F\left(1\right)=1 \) ו-\( F\left(n\right)=F\left(n-1\right)+F\left(n-2\right) \) לכל \( n\ge2 \); גם בשביל לחשב את \( F\left(100\right) \) צריך לחשב קודם כל את כל האיברים הקודמים, ועדיין החישוב הוא פשוט יחסית (יש גם נוסחה סגורה לפיבונאצ’י, אבל זה לא אומר שיותר קל להשתמש בה בחישובים).

ובכן, מה אם אספר לכם שאפשר לחשב את פונקציית החלוקה באופן רקורסיבי שכזה, אבל במקום לחבר את כל ה-\( p\left(k\right) \)-ים עבור \( k<n \), צריך לחבר (או לחסר) רק חלק מהם? למשל, \( p\left(4\right)=p\left(3\right)+p\left(2\right) \); ואם תבדקו בעזרת הרשימה שנתתי לעיל תוכלו גם לראות ש-

\( p\left(5\right)=p\left(4\right)+p\left(3\right)-p\left(0\right) \)

\( p\left(6\right)=p\left(5\right)+p\left(4\right)-p\left(1\right) \)

וכך זה נמשך אבל הולך ומסתבך מבחינת “את מי לחבר/לחסר”. למשל:

\( p\left(17\right)=p\left(16\right)+p\left(15\right)-p\left(12\right)-p\left(10\right)+p\left(5\right) \)

מה החוקיות הכללית פה? כאן נכנס לתמונה מי שנקראים מספרים מחומשים. מספר מחומש \( t\left(k\right) \) הוא מספר מהצורה \( t\left(k\right)=\frac{k\left(3k-1\right)}{2} \) עבור \( k \) שלם ששונה מאפס - חיובי או שלילי (האות \( t \) היא לא סימון סטנדרטי; אני משתמש בה כי הסימון הסטנדרטי משתמש ב-\( p \) שכבר תפוס לתיאור חלוקות). הרעיון הוא שכדי לחשב את \( p\left(n\right) \) סוכמים את כל האיברים מהצורה \( p\left(n-t\right) \) כאשר \( t \) הוא מספר מחומש שקטן מ-\( n \); השאלה האם לחבר או לחסר את \( p\left(n-t\right) \) תלויה בזוגיות של ה-\( k \) שהניב אותו: אם הוא אי-זוגי, אז מחברים, ואם הוא זוגי אז מחסרים. אם נשב לכתוב את סדרת המספרים המחומשים נראה שהיא שווה ל

\( 1,2,5,7,12,15,22,26,\dots \)

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

\( p\left(n\right)=p\left(n-1\right)+p\left(n-2\right)-p\left(n-5\right)-p\left(n-7\right)+p\left(n-12\right)+p\left(n-15\right)-p\left(n-22\right)-p\left(n-26\right)+\dots \)

וכן הלאה וכן הלאה. זו תוצאה מרהיבה ממש לטעמי (בפרט קל להעריך אותה אם מנסים לחשב מספרית את \( p\left(n\right) \) בדרכים אחרות ורואים עד כמה זה מעיק), אבל היא נראית גם הזויה לחלוטין - מה המשמעות הקומבינטורית של נוסחת הנסיגה הזו? למה מחברים או מחסרים? למה דווקא המספרים ה”מחומשים” הללו? ובכן, הפוסט הזה ינסה לענות על השאלות הללו ברמה כלשהי, אם כי אני מזהיר מראש שאין לי אינטואיציה קומבינטורית לגבי “למה הנוסחה עובדת”; אני הולך להוכיח אותה בעזרת כלי קומבינטורי חזק מאוד שנקרא פונקציות יוצרות. הכלי הזה נותן לי תחושה חזקה מאוד של “למה זה נכון”, ועם זאת לא נותן לי שום רמז לגבי משמעות קומבינטורית אפשרית של נוסחת הנסיגה. זה פחות מפריע לי כי אני חושב שהבעיה הספציפית הזו של חלוקות היא הזדמנות מושלמת להראות מה הן פונקציות יוצרות ומה הכוח שלהן.

את הסיפור של פונקציית החלוקה שאני רוצה לספר אפשר לתמצת לשתי משוואות שבמבט ראשון יכולות להיראות חסרות פשר, אפילו שגויות, וננסה להבין אותן כאן:

• \( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)} \)
• \( \prod_{n=1}^{\infty}\left(1-x^{n}\right)=\sum_{k=-\infty}^{\infty}\left(-1\right)^{k+1}x^{t\left(k\right)} \)

הנוסחה הראשונה עוסקת בפונקציה היוצרת של הפונקציה \( p \) של מספר החלוקות, והשניה איכשהו מכניסה פנימה את הפונקציה \( t\left(k\right) \) של המספרים המחומשים. הקישור של שתיהן יחד נותן לנו את נוסחת הנסיגה שראינו קודם. אנחנו נרצה לעשות שלושה דברים:

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

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

פרק שני, ובו בהחלט לא נעסוק בחדו"א בשום צורה

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

\( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)} \)

מה זה \( \sum_{n=0}^{\infty}p\left(n\right)x^{n} \)? יש כאן סכום אינסופי, יצור שאנחנו רגילים אליו מחדו”א. בחדו”א מדברים על טורי מספרים, למשל הטור \( \sum_{n=1}^{\infty}\frac{1}{2^{n}} \). יש הגדרות מקובלות שמתבססות על מושג הגבול שאומרות מתי סביר להתאים ערך של “סכום” לטור כזה ומתי לא - בהגדרות הללו יוצא, למשל, ש-\( \sum_{n=1}^{\infty}\frac{1}{2^{n}}=1 \). מכירים את זה? מצויין. אז אני מבקש מכם לשכוח את זה לגמרי בפוסט הזה. לא נדבר על מושג הגבול ולא נזדקק לו ולא נזדקק לחדו”א. לא על זה מדובר פה.

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

בואו ניתן עוד מבט בסכום:

\( \sum_{n=0}^{\infty}p\left(n\right)x^{n} \)

כאן סוכמים לא רק מספרים, אלא גם חזקות של המשתנה \( x \). זה מזכיר את המושג של טור חזקות מחדו”א, ואני אכן קורא ליצור הזה טור חזקות פורמלי, אלא שאני שוב רוצה להסתייג - הרעיון בטורי חזקות הוא שאפשר להציב ערכים שונים ומשונים בתוך \( x \), לקבל טור מספרים רגיל ואז לראות האם הוא מתכנס, ואל מה. אני לא הולך לעשות את זה - בשום מקום בהמשך לא נציב משהו בתוך \( x \). אז רגע - אם לא מציבים כלום בתוך \( x \), בשביל מה הוא כאן? האם זה סתם סימון? דרך מסובכת לכתוב את הסדרה \( \left(p\left(0\right),p\left(1\right),p\left(2\right),\dots\right) \)? ובכן, זו אכן רק דרך לכתוב את הסדרה הזו, אבל אני טוען שלא דרך מסובכת אלא ההפך - דרך יותר פשוטה.

בואו ניזכר לרגע בפולינומים. את הפולינום \( x^{3}+2x^{2}+4 \) אפשר גם לכתוב בתור סדרה: \( \left(4,0,2,1\right) \). אפשר לראות שאם אחד המקדמים הוא 0, אז הפולינום “חסכוני” יותר בכך שלא חייבים לכתוב את האיבר שמתאים לו, אבל זה לא כזה קריטי. החלק המעניין מתחיל אם אני רוצה לכפול את הפולינום הזה בפולינום אחר. למשל:

\( \left(x^{3}+2x^{2}+4\right)\left(x^{2}+1\right)=\left(x^{5}+2x^{4}+4x^{2}\right)+\left(x^{3}+2x^{2}+4\right)= \)

\( =x^{5}+2x^{4}+x^{3}+6x^{2}+4 \)

כאן הכפל קל יחסית כשפותחים סוגריים ומשתמשים בכלל החזקות \( x^{a}\cdot x^{b}=x^{a+b} \), שהוא מבחינתנו כאן הגדרה ולא משהו שיש להוכיח. בואו נסתכל עכשיו איך זה נראה בתור “כפל סדרות”:

\( \left(4,0,2,1\right)\times\left(1,0,1\right)=\left(4,0,6,1,2,5\right) \)

לא לגמרי ברור פה איך אגף ימין התקבל מאגף שמאל. הכלל שעל פיו החישוב מתבצע נקרא קונבולוציה, וזה הולך כך: אם \( \left(a_{1},a_{2},\dots,a_{n}\right) \) ו-\( \left(b_{1},\dots,b_{m}\right) \) הן סדרות אז נגדיר את הקונבולוציה שלהן

\( \left(a_{1},\dots,a_{n}\right)*\left(b_{1},\dots,b_{m}\right)=\left(c_{1},\dots,c_{n+m}\right) \)

על ידי הכלל \( c_{k}=\sum_{i=1}^{k}a_{i}b_{m-i} \) (תוך המוסכמה ש-\( b_{i}=0 \) עבור \( i\le0 \)). נראה מבלבל? בהחלט, אבל זו בסך הכל דרך “נטולת \( x \)” לתאר את פעולת הכפל הרגילה של פולינומים. כך שהייצוג ה”מיותר” של הפולינום הוא דווקא מועיל בכך שהוא נותן לנו אינטואיציה יותר טובה לפעולת הכפל.

עכשיו בואו נדבר על כפל של שני טורים אינסופיים, \( \sum_{n=0}^{\infty}a\left(n\right)x^{n} \) ו-\( \sum_{n=0}^{\infty}b\left(n\right)x^{n} \). על פניו אפשר לחשוש שאם הטורים לא “מתכנסים” אז אסור להכפיל אותם או משהו דומה לכך, אבל אם שמים את זה בצד ופשוט כופלים אותם כמו כפל פולינומים רגיל, מגלים שהתוצאה היא טור \( \sum_{n=0}^{\infty}c\left(n\right)x^{n} \) שכל איבר בו מוגדר על ידי המשוואה

\( c\left(n\right)=\sum_{k=0}^{n}a\left(k\right)b\left(n-k\right) \)

(שוב, תחת המוסכמה ש-\( b\left(t\right)=0 \) אם \( t<0 \)).

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

כדי לתרגל לרגע את הכפל, בואו נסתכל על טור החזקות הפורמלי \( \sum_{n=0}^{\infty}a\left(n\right)x^{n} \) שבו \( a\left(n\right)=1 \) לכל \( n \), ועל הטור \( \sum_{n=0}^{\infty}b\left(n\right)x^{n} \) שבו \( b\left(0\right)=1 \) ו-\( b\left(1\right)=-1 \) ו-\( b\left(n\right)=0 \) לכל \( n>1 \). אפשר לכתוב אותם בצורה מקוצרת כך: \( \left(1+x+x^{2}+\dots\right) \) לטור הראשון ו-\( 1-x \) לטור השני. אם נכפול את שניהם, קל לראות שנקבל לכל \( n>0 \) את האיבר הכללי:

\( c\left(n\right)=\sum_{k=0}^{n}a\left(k\right)b\left(n-k\right)=a\left(n-1\right)b\left(1\right)+a\left(n\right)b\left(0\right)=-1+1=0 \)

ואילו עבור \( n=0 \) נקבל איבר כללי \( c\left(n\right)=1 \). אפשר לכתוב את זה כך:

\( \left(1+x+x^{2}+\dots\right)\left(1-x\right)=1 \)

וזה מוביל לעוד מוסכמת כתיבה שאני מבקש שתהיו סלחניים אליה:

\( \left(1+x+x^{2}+\dots\right)=\frac{1}{1-x} \)

אתם אולי מכירים את השוויון הזה בתור “סכום טור הנדסי אינסופי מתכנס”, אבל שוב אני רוצה להזהיר שאני לא מדבר פה על התכנסויות במובן של חדו”א! אגף ימין כאן הוא סימון מקוצר; זו דרך להגיד “טור החזקות הפורמלי שכאשר כופלים אותו ב-\( \left(1-x\right) \) מקבלים 1”. באופן כללי אם

\( \sum a\left(n\right)x^{n}\cdot\sum b\left(n\right)x^{n}=\sum c\left(n\right)x^{n} \)

אפשר יהיה לכתוב את זה גם בתור

\( \sum a\left(n\right)x^{n}=\frac{\sum c\left(n\right)x^{n}}{\sum b\left(n\right)x^{n}} \)

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

\( \left(1+x^{n}+x^{2n}+x^{3n}+\dots\right)=\frac{1}{1-x^{n}} \)

לכל \( n \) טבעי. למשל

\( \left(1+x^{2}+x^{4}+\dots\right)=\frac{1}{1-x^{2}} \)

\( \left(1+x^{3}+x^{6}+\dots\right)=\frac{1}{1-x^{3}} \)

אפשר עכשיו לכפול את שתי המשוואות, ונקבל:

\( \left(1+x^{2}+\dots\right)\left(1+x^{3}+\dots\right)=\frac{1}{\left(1-x^{2}\right)}\cdot\frac{1}{\left(1-x^{3}\right)} \)

כמובן, צריך לבדוק שזה אכן עובד, פורמלית, אבל זה עובד. ואם זה עובד לשני מוכפלים, זה יעבוד לכל מספר סופי של מוכפלים, אבל אנחנו נהיה שאפתנים אפילו יותר ונעשה את זה עבור אינסוף מוכפלים! אבל לפני זה, בואו ננסה להבין מה בעצם המשמעות הקומבינטורית של הכפלה כזו, כי זה בדיוק מה שיתן לנו את השוויון \( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)} \) שאנחנו חותרים אליו.

בדוגמה שלנו, אם נפתח את הסוגריים של המכפלה נקבל את המחוברים הבאים: \( 1\cdot1+x^{2}\cdot1+1\cdot x^{3}+x^{2}\cdot x^{3}+x^{4}\cdot1+\dots \). זה בסך הכל שווה ל-\( 1+x^{2}+x^{3}+x^{4}+x^{5}+2x^{6}+\dots \) - רגע רגע רגע, מאיפה הגיע המקדם 2 ל-\( x^{6} \)? ובכן, כי הוא נוצר בעזרת שני מוכפלים כי הוא מופיע בשני זוגות הסוגריים. אפילו יותר מעניין יהיה \( x^{12} \) שיכול להיווצר בדרכים הבאות: \( x^{12}\cdot1,1\cdot x^{12},x^{6}\cdot x^{6} \), ולכן המקדם שלו יהיה 3, וכן הלאה. אנחנו רואים שהמקדם של \( x^{n} \) סופר את הדרכים השונות שבהן ניתן לכתוב את \( n \) בתור סכום מהצורה \( n=2a+3b \). כל דרך שכזו נותנת לנו איבר מפורש, \( x^{2a}\cdot x^{3b}=x^{n} \) שיתווסף לסכום.

הנה הפרשנות הקומבינטורית של הסיפור הזה. נניח שיש בעולם שלנו אובייקטים מגדלים שונים ומשונים שהם מספר טבעי, וש-\( \sum a\left(n\right)x^{n} \) סופר חלק מהם - בדיוק \( a\left(n\right) \) אובייקטים מ”גודל” \( n \). באופן דומה \( \sum b\left(n\right)x^{n} \) סופר קבוצה אחרת של אובייקטים שכאלה. במקרה שלנו האובייקטים הם חלוקות של מספרים טבעיים כשה”גודל” של חלוקה הוא סכום האיברים שלה; \( \sum x^{2n} \) סופר לנו כמה פירוקים לסכום של 2 בלבד יש (או 0 או 1, תלוי אם המספר זוגי) ו-\( \sum x^{3n} \) סופר כמה פירוקים לסכום של 3 בלבד יש (שוב, או 0 או 1, תלוי אם המספר מתחלק ב-3 או לא). למשל \( x^{6} \) במקרה הראשון מציין את הפירוק \( 2+2+2 \) ובמקרה השני את הפירוק \( 3+3 \).

כעת, מכפלה של שתי פונקציות יוצרות מתאימה לבניה הקומבינטורית הבאה: לכל זוג אפשרי של אובייקט מסוג ראשון ואובייקט מסוג שני אנחנו בונים אובייקט חדש ש”מורכב מהם” והגודל שלו הוא סכום הגדלים שלהם. אם אין אובייקט שיכול להתקבל משני זוגות שונים, אז הפונקציה היוצרת של המכפלה סופרת בדיוק כמה אובייקטים יכולים להיווצר ככה. כך למשל אצלנו האיבר \( x^{10} \) במכפלה, שאומר “חלוקה אחת של 10” נוצר מזוג החלוקות \( 2+2 \) ו-\( 3+3 \), שמתאימות לאיברים \( x^{4} \) ו-\( x^{6} \) בפונקציות היוצרות הראשונה והשניה. באופן דומה, המקדם של \( x^{3} \) הוא 1, שמציין את האופן שבו אפשר ליצור את \( 3 \) מהחלוקות “3” ו-“0” (כלומר, מחברים 3 פעם אחת, ומחברים 2 אפס פעמים).

אם נכפול עכשיו שלוש פונקציות יוצרות, המשמעות תישאר זהה: איברים שאפשר לבנות על ידי לקיחה של שלשה של אובייקטים והרכבה שלהם ביחד. למשל, את \( 4 \) אפשר להציג בתור החלוקות הבאות:

\( 4 \)

\( 2+2 \)

\( 1+3 \)

\( 1+1+2 \)

אז אם אני אפתח את המכפלה

\( \left(1+x+x^{2}+\dots\right)\left(1+x^{2}+x^{4}+\dots\right)\left(1+x^{3}+x^{6}+\dots\right) \)

אני אקבל את המקדם \( 3x^{4} \), שמייצג את שלוש החלוקות שבהן משתתפים רק 1,2,3; החלוקה 4 תתקבל רק אם אוסיף למכפלה גם את \( \left(1+x^{4}+x^{8}+\dots\right) \).

עכשיו אוילר אומר שני דברים. ראשית, במקום לכתוב סימון ארוך ומסורבל כמו \( \left(1+x^{t}+x^{2t}+\dots\right) \) כל פעם מחדש, בואו נכתוב \( \frac{1}{\left(1-x^{t}\right)} \); כבר ראינו שזה אותו דבר. שנית, על פי הנימוק שנתנו כאן \( \prod_{t=1}^{k}\frac{1}{\left(1-x^{t}\right)} \) ייתן לנו את הפונקציה היוצרת של מספר הדרכים לחלק כל מספר טבעי לסכום של מספרים מ-1 ועד \( k \), כלומר את מספר הפתרונות של המשוואה \( 1\cdot x_{1}+2\cdot x_{2}+\dots+k\cdot x_{k}=n \), לכל \( n \) טבעי. יש התאמה חד-חד-ערכית ועל ברורה בין פתרונות כאלו לבין האיברים שמתקבלים מפתיחת המכפלה \( \prod_{t=1}^{k}\left(1+x^{t}+x^{2t}+\dots\right) \): הפתרון \( x_{1}=a_{1},\dots,x_{k}=a_{k} \) מתאים לאיבר

\( x^{a_{1}\cdot1}\cdot x^{a_{2}\cdot2}\cdots x^{a_{k}\cdot k}=x^{a_{1}\cdot1+\dots+a_{k}\cdot k}=x^{n} \). אני חוזר על זה במפורש כל כך כי הצעד הבא של אוילר הוא לעבור לדבר על המכפלה האינסופית \( \prod_{t=1}^{\infty}\frac{1}{\left(1-x^{t}\right)} \) ולטעון שהיא נותנת את הפונקציה היוצרת של חלוקות כלליות. אני מקווה שזה נשמע לנו אינטואיטיבי בשלב הזה, אבל מה בכלל המשמעות של מכפלה אינסופית שכזו? אי אפשר סתם לומר “כל האיברים שמתקבלים מפתיחת כל הסוגריים” כי דבר כזה יכלול “איברים” כמו \( x\cdot x^{2}\cdot x^{3}\cdots \) שהחזקה שלהם יוצאת בעצמה סכום של מספרים טבעיים שאינו מתכנס (או שמתכנס ל-\( -\frac{1}{12} \) אם ממש בא לכם, אבל זה לא מקדם אותנו). האינטואיציה שלנו היא שהאיברים היחידים ש”נחשבים” הם כאלו שכאשר פותחים את הסוגריים, מתקבלים רק ממספר סופי של מוכפלים שאינם 1. זה כמובן מה שקורה אצלנו.

אם זה לא פורמלי מספיק בשבילכם, הנה פסקה טכנית במיוחד שאני מקווה שתספיק לכם. צריך לקבל כאן מוסכמה כלשהי כדי לתת משהו לסימון הזה של מכפלה אינסופית - והמוסכמה היא שההגדרה של כפל תישאר בדיוק מה שהייתה במקרה הסופי. במקרה הסופי, הגדרנו \( \sum a_{n}\cdot\sum b_{n}=\sum c_{n} \) כך ש-\( c_{n}=\sum_{k=0}^{n}a_{n}b_{n-k} \). אפשר לנסח את זה גם טיפה שונה: \( c_{n}=\sum_{k_{1}+k_{2}=n}a_{k_{1}}b_{k_{2}} \). כלומר, אנחנו עוברים על כל הפירוקים של \( n \) לסכום שני טבעיים ומחברים את האיברים המתאימים ב-\( \sum a_{n} \) ו-\( \sum b_{n} \) עבורם. את זה קל להכליל לשלושה איברים: \( d_{n}=\sum_{k_{1}+k_{2}+k_{3}=n}a_{k_{1}}b_{k_{2}}c_{k_{3}} \) וכן הלאה. עבור מכפלה אינסופית \( \prod_{k=1}^{\infty}\left(\sum a_{n}^{k}\right) \), האיבר ה-\( n \) יהיה שווה לסכום של כל האיברים מהצורה \( a_{t_{1}}^{k_{1}}\cdots a_{t_{r}}^{k_{r}} \) כך ש-\( t_{1}+\dots+t_{r}=n \) ואילו \( \left(k_{1},\dots,k_{r}\right) \) היא בחירה שרירותית כלשהי של \( r \) טבעיים, כשהם מסודרים מהקטן לגדול. כל איבר בסכום הזה הוא בהכרח סופי כי הוא מכפלה סופית, אבל כדי שהעסק יהיה בעל משמעות צריך שיהיה רק מספר סופי של איברים בסכום הזה; כלומר, רק מספר סופי של בחירות \( \left(k_{1},\dots,k_{r}\right) \) שעבורן מתקבל \( a_{t_{1}}^{k_{1}}\cdots a_{t_{r}}^{k_{r}}\ne0 \). אם זה לא המצב, אז המכפלה לא מוגדרת.

נסכם: המכפלה האינסופית סופרת, לכל \( n \), את מספר הפתרונות של המשוואה \( 1\cdot x_{1}+2\cdot x_{2}+3\cdot x_{3}\dots=n \). פתרונות כאלו מראש מאלצים אותנו לתת 0 לכל המשתנים למעט מספר סופי; זה יתאים למכפלות שמתקבלות מפתיחת הסוגריים \( \left(1+x+x^{2}+\dots\right)\left(1+x^{2}+x^{4}+\dots\right) \) שבהן רק מספר סופי של מוכפלים הם של חזקות שונות מאפס, כלומר בוחרים “1” מכל הסוגריים למעט מספר סופי שלהן. זה מה שנותן לנו את המשוואה \( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)} \). כמובן שאם זה עדיין מרגיש “שגוי”, כדאי לבצע את החישוב עצמאית, בעזרת ההגדרות שנתתי פה - זה יספיק.

פרק שלישי, שבו אולי יתברר למה השתלם לשרוד את כל הזוועות הטכניות הקודמות

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

מה זו פונקציה רציונלית? מנה של שני פולינומים, כלומר משהו מהצורה \( \frac{s_{k}x^{k}+\dots+s_{1}x+s_{0}}{r_{t}x^{n}+\dots+r_{1}x+r_{0}} \). למשל, \( \frac{1}{1-x} \) שראינו קודם היא פונקציה רציונלית. הנה עוד אחת: \( \frac{1}{1-x-x^{2}} \). מזהים את הסדרה שקשורה אליה? לא? אוקיי, אז בואו נסמן אותה בינתיים בתור \( a_{n} \), כרגיל; יש לנו את המשוואה \( \sum_{n=0}^{\infty}a_{n}x^{n}=\frac{1}{1-x-x^{2}} \). עכשיו, מה השוויון הזה אומר, פורמלית? שאם אכפול את אגף שמאל ב-\( 1-x-x^{2} \) אקבל 1. כלומר:

\( \left(\sum_{n=0}^{\infty}a_{n}x^{n}\right)\left(1-x-x^{2}\right)=1 \)

אם נפתח את הסוגריים ונקבץ איברים, נקבל את הסכום הבא:

\( 1\cdot x^{0}+0\cdot x^{1}+0\cdot x^{2}+0\cdot x^{3}+\dots=\left(a_{0}\right)x^{0}+\left(a_{1}-a_{0}\right)x+\left(a_{2}-a_{1}-a_{0}\right)x^{2}+\left(a_{3}-a_{2}-a_{1}\right)x^{3}+\dots \)

בדקו זאת! זה נובע ישירות מההגדרות שכבר ראינו. עכשיו, מה שבעצם קיבלנו הוא אינסוף משוואות, שמתקבלות מהשוואת המקדמים לכל חזקה של \( x \). כלומר, קיבלנו:

• \( a_{0}=1 \)
• \( a_{1}-a_{0}=0 \)
• \( a_{2}-a_{1}-a_{0}=0 \)
• \( a_{3}-a_{2}-a_{1}=0 \)

וכן הלאה. שתי המשוואות הראשונות נותנות לנו \( a_{0}=a_{1}=1 \) ואילו האחרות נותנות לנו \( a_{n}=a_{n-1}+a_{n-2} \) באופן כללי. מזהים כעת? זו כמעט סדרת פיבונאצ’י: יש לה את נוסחת הנסיגה של פיבונאצ’י אבל תנאי התחלה ששוכחים את האיבר הראשון ה”אמיתי” שהוא \( 0 \). האם אפשר איכשהו לתקן את זה? בוודאי. בואו נסתכל על הפונקציה היוצרת \( \frac{x}{1-x-x^{2}} \) שזהה לזו שראינו קודם פרט לכך שכפלנו את המונה ב-\( x \). כעת נקבל משוואות שמתחילות ב-

• \( a_{0}=0 \)
• \( a_{1}-a_{0}=1 \)
• \( a_{2}-a_{1}-a_{0}=0 \)

וכן הלאה. ההבדל הוא בעצם רק באופן שבו שני האיברים הראשונים הוגדרו, וגם שם - רק במה שהיה באגף ימין.

בשתי הדוגמאות הללו בעצם מצויה כל התורה כולה: אם יש לנו פונקציה יוצרת רציונלית, המקדמים של המכנה מכתיבים לנו את נוסחת הנסיגה של הסדרה, בעוד שהמקדמים של המונה מכתיבים לנו את תנאי ההתחלה של הסדרה. אם המכנה הוא \( r_{t}x^{n}+\dots+r_{1}x+r_{0} \) והמונה הוא \( s_{k}x^{k}+\dots+s_{1}x+s_{0} \), זה נותן לנו את הנוסחה הכללית

\( r_{0}a_{n}+r_{1}a_{n-1}+\dots+r_{t}a_{n-t}=s_{n} \)

עבור \( n \) גדול מספיק, \( s_{n}=0 \) תמיד, אז אנחנו מקבלים:

\( r_{0}a_{n}=-r_{1}a_{n-1}-\dots-r_{t}a_{n-t} \)

זה מסביר את מה שקרה קודם - איך \( 1-x-x^{2} \) נתן לנו את נוסחת הנסיגה \( a_{n}=a_{n-1}+a_{n-2} \) שאין בה מינוסים. הסימן של כל המקדמים למעט זה של החזקה הקטנה ביותר מתהפכים כשמבצעים את העברת האגף הזו.

עוד נקודה שכדאי לשים לב אליה היא שנוסחת הנסיגה הזו עובדת תמיד, לכל \( n \), גם כאלו קטנים. בואו נחזור לפיבונאצ’י: קודם כתבתי

\( a_{0}=1 \)

\( a_{1}-a_{0}=0 \)

אבל יכלתי באותה מידה בדיוק לכתוב

\( a_{0}-a_{-1}-a_{-2}=1 \)

\( a_{1}-a_{0}-a_{-1}=0 \)

תחת המוסכמה ש-\( a_{-1}=a_{-2}=0 \). זה היה נותן מבנה אחיד לכל אגפי שמאל של המשוואות; ההבדל היחיד הוא באגף ימין, שמוכתב על ידי המונה של הפונקציה היוצרת.

אני מתעקש כל כך על דרך ההצגה הזו, כי עכשיו אני רוצה לעבור לדבר על המקרה שבו המונה והמכנה הם אינסופיים, כלומר אנחנו בסיטואציה הכללית שתיארתי קודם: \( \sum a_{n}x^{n}=\frac{\sum c_{n}x^{n}}{\sum b_{n}x^{n}} \). גם במקרה הזה הניתוח שעשינו קודם עובד - אני אקבל משוואות, פשוט קצת יותר מסובכות. הנה המשוואה הכללית:

\( b_{0}a_{n}+b_{1}a_{n-1}+\dots+b_{n}a_{0}+b_{n+1}a_{-1}+\dots=c_{n} \)

מכיוון שההנחה היא ש-\( a_{-1}=a_{-2}=\dots=0 \), אפשר למחוק את האיברים הללו מהסכום. אנחנו מקבלים משוואה עם מספר סופי של מחוברים

\( b_{0}a_{n}+b_{1}a_{n-1}+\dots+b_{n}a_{0}=c_{n} \)

קשה לומר שהמשוואה הזו היא מה שאנחנו חושבים עליו בתור נוסחת נסיגה, בגלל שתי בעיות: ראשית, \( a_{n} \) הופך כאן לתלוי בכל האיברים שבאים לפניו בסדרה ולא רק בשניים-שלושה קודמים. אבל זה עוד בסדר איכשהו. הבעיה העיקרית היא עם ה-\( c_{n} \)-ים הללו באגף ימין, שקצת מוציאים את העוקץ מכל הסיפור אם הם לא פשוטים מספיק. הרי אם ה-\( c_{n} \)-ים מסובכים, המרנו את הבעיה של לכתוב נוסחה מסודרת לערכים של \( a_{n} \) בבעיה של לכתוב נוסחה מסודרת לערכים של \( c_{n} \) ולא הרווחנו כלום. לכן פחות מעניין אותי המקרה של מונה אינסופי; אבל בהחלט אפשר לדבר על מה קורה כשהמונה סופי (בתקווה, 1) ואילו המכנה אינסופי. זה בדיוק המקרה של נוסחת הנסיגה שלנו עבור פונקציית החלוקה.

סיכום ביניים, ובו אני מתפייט על מה שעבורי כרגע היא הנוסחא היפה במתמטיקה

בואו נחזור אל שתי הנוסחאות שאיתן פתחנו:

• \( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{n=1}^{\infty}\frac{1}{\left(1-x^{n}\right)} \)
• \( \prod_{n=1}^{\infty}\left(1-x^{n}\right)=\sum_{k=-\infty}^{\infty}\left(-1\right)^{k+1}x^{t\left(k\right)} \) (כאשר \( t\left(k\right)=\frac{k\left(3k-1\right)}{2} \))

הנוסחה השניה היא פשוט ההופכי של אגף ימין של הראשונה, כך שאם נשלב את שתי הנוסחאות ונכתוב את השניה במפורש, נקבל:

\( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\frac{1}{1-x-x^{2}+x^{5}+x^{7}-x^{12}-\dots} \)

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

\( p\left(n\right)=p\left(n-1\right)+p\left(n-2\right)-p\left(n-5\right)-p\left(n-7\right)+p\left(n-12\right)+\dots \)

זה משאיר אותנו רק עם השאלה איך מוכיחים את הנוסחה השניה - זה לב העניין כאן והתוצאה היפה באמת לטעמי. אני אדבר על זה בפוסט הבא, אבל כבר עכשיו אפשר לקבל רעיון כללי לגבי מה בעצם הולך פה. כשפותחים את הביטוי \( \prod_{k=1}^{\infty}\left(1-x^{k}\right) \), מה מקבלים? על פי שיקולים דומים לאלו שראינו קודם, הגורם \( x^{n} \) מתקבל עבור כל חלוקה של \( n \) למחוברים שונים, כשהסימן שלו הוא פלוס או מינוס בהתאם לזוגיות של מספר המחוברים. למשל, \( x^{3} \) מתקבל מ-\( \left(1-x\right)\left(1-x^{2}\right)\left(1-x^{3}\right) \) בדיוק בשתי דרכים: הראשונה, כאשר אנחנו בוחרים משני הסוגריים הראשונים 1 ומהסוגריים האחרונים את \( -x^{3} \), ואז נקבל סימן שלילי; ואילו אם נבחר מהסוגריים הראשונים את \( -x \) ומהשניים את \( -x^{2} \) ומהאחרונים את \( 1 \) נקבל \( \left(-x\right)\left(-x^{2}\right)=x^{3} \) והפעם קיבלנו סימן חיובי. מכיוון ששני אלו בעלי סימנים מנוגדים, הם מבטלים זה את זה כאשר מחברים אותם, ואנחנו לא מקבלים את \( x^{3} \) בכלל בסכום הסופי.

מה קורה עם \( x^{5} \)? הנה הפירוקים שלו למספרים שונים: \( 5,1+4,2+3 \). כאן יש יתרון לפירוק למספר זוגי של מחוברים, ולכן הגורם \( x^{5} \) יוצא חיובי בסכוםּ. לעומת זאת \( 6 \) לא מופיע בסכום כי יש לו את הפירוקים \( 6,1+5,2+4,1+2+3 \) - שניים זוגיים, שניים אי זוגיים, הכל מתבטל.

אם כן, את משפט המספרים המחומשים אפשר גם לנסח באופן הבא: לכל מספר טבעי \( n \), נסמן ב-\( p_{\text{odd}}\left(n\right) \) את מספר הפירוקים שלו לסכום מספרים שונים עם מספר אי זוגי של מחוברים, וב-\( p_{\text{even}}\left(n\right) \) את מספר הפירוקים לסכום מספרים שונים עם מספר זוגי של מחוברים. המשפט אומר שבדרך כלל \( p_{\text{odd}}\left(n\right)=p_{\text{even}}\left(n\right) \), כשהיוצאים מן הכלל הם המספרים המחומשים, ובמקרה שלהם אחד משני המספרים יהיה גדול בדיוק ב-1 מהשני. במקרה שבו המספר המחומש הוא \( \frac{k\left(3k-1\right)}{2} \) עם \( k \) אי-זוגי אז מי שיהיה גדול יותר הוא \( p_{\text{odd}}\left(n\right) \), ובמקרה השני זה יהיה \( p_{\text{even}}\left(n\right) \).

הנוסחה \( \prod_{n=1}^{\infty}\left(1-x^{n}\right)=\sum_{k=-\infty}^{\infty}\left(-1\right)^{k+1}x^{\frac{k\left(3k-1\right)}{2}} \) מקסימה לטעמי בגלל שהיא תופסת בצורה מאוד קומפקטית את המשפט הזה, על כל הסיבוך של הפירוק לסכום מחוברים, והספירה של כמה מחוברים יש וכן הלאה. אני לא חובב גדול של נוסחאות, אבל לטעמי הנוסחא הזו צריכה להופיע בכל רשימת “הנוסחאות היפות ביותר במתמטיקה” (מה שכמובן לא קורה). נו טוב.

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