אני רוצה להמשיך לדבר על פונקציות יוצרות והדברים המגניבים שעושים איתן, ובפוסט הזה ללכת לכיוונים עוד יותר טכניים מהפוסט הקודם (כי ככה זה במתמטיקה – כשמגיעים לדברים מתוחכמים, זה גם נהיה יותר טכני). בפוסט הקודם ראינו כי אם \(A,B\) הן מחלקות של אובייקטים עם פונקציות יוצרות \(a\left(x\right),b\left(x\right)\) אז הפונקציה היוצרת של \(A+B\) (איחוד זר של \(A,B\)) היא \(a\left(x\right)+b\left(x\right)\); הפונקציה היוצרת של \(A\times B\) היא \(a\left(x\right)b\left(x\right)\); והפונקציה היוצרת של \(A^{*}\) (סדרות סופיות של איברים מ-\(A\)) היא \(\frac{1}{1-a\left(x\right)}\). עם שלוש הבניות הללו כבר יצא לנו לפתור בעיה נחמדה באופן לא טריוויאלי (ספירה של עצים) – בואו נוסיף עוד כמה כלים לארסנל ונראה איך הם עוזרים לנו.

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

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

וכשנפתח את הסוגריים, האיבר \(x^{n}\) יתקבל בדיוק כמספר הפתרונות בטבעיים של המשוואה \(y_{1}+2y_{2}=n\) (הסבירו לעצמכם מדוע!)

כבר אוילר הלך עם החשיבה הזו צעד אחד קדימה ואמר שאם כך, הפונקציה היוצרת עבור חלוקות בכלל, שבהן אין לנו מגבלה על גודל החלקים שאליהם אפשר לפרק את \(n\), הוא פשוט המכפלה \(\prod_{m=1}^{\infty}\frac{1}{1-x^{m}}\) (הסימן \(\Pi\) מציין מכפלה – אנחנו כופלים את כל האיברים מהצורה \(\frac{1}{1-x^{m}}\), עבור כל \(m\ge1\) טבעי). מכפלה אינסופית שכזו עשויה לגרום להרמת גבה, אבל כרגיל – טור החזקות שהוא תוצאת הכפל הוא בעל התכונה שכל מקדם שלו נקבע רק על פי מספר סופי של איברים, ולכן אין לנו כאן צורך לדבר על התכנסות בכלל והאינסופים שנכנסים למשחק לא משפיעים עלינו. זה נפנוף ידיים שמסתיר מאחוריו קצת יותר סיבוכים שלא אכנס אליהם.

הדוגמה הזו היא מקרה פרטי של בניה כללית שאכנה Multiset, ובקיצור – \(\mbox{MS}\). אם \(A\) היא מחלקה כלשהי, אז פורמלית אפשר להגדיר את \(\mbox{MS}\left(A\right)\) בתור \(\prod_{a\in A}\left\{ a\right\} ^{*}\) כאשר איברים "אינסופיים" מוצאים החוצה (הסבר מדויק יבוא אחרי שנבין מה לעזאזל הולך בהגדרה הבסיסית). בניסוח מילולי, איבר של \(\mbox{MS}\left(a\right)\) מורכב ממספר סופי של סדרות, כשבכל סדרה מופיע איבר כלשהו של \(A\) מספר סופי מסויים של פעמים.

ברור לי שגם התיאור הזה אבסטרקטי למדי אז הנה דוגמה קונקרטית. אפשר לחשוב על הטבעיים, \(\mathbb{N}=\left\{ 1,2,3,\dots\right\} \), בתור קבוצה של אובייקטים קומבינטוריים כאשר ה"גודל" של איבר \(t\in\mathbb{N}\) הוא פשוט \(t\) עצמו (כלומר, יש איבר בודד מגודל 1 – המספר 1; ואיבר בודד מגודל 13 – המספר "שלוש עשרה", וכן הלאה). לפורמליסטיים שבכם רק אעיר שאפשר להגדיר את \(\mathbb{N}\) הזו בתור \(\left\{ \bullet\right\} \cdot\left\{ \bullet\right\} ^{*}\), כאשר \(\bullet\) הוא סימון מוסכם לאיבר מגודל 1 ("אטום").

כעת, מהו \(\mbox{MS}\left(\mathbb{N}\right)\)? איבר לדוגמה בו ייראה כך: \(\left(\left(1,1,1\right),\left(2,2\right),\left(7\right),\left(13,13\right)\right)\) – זה אוסף של 4 סדרות; בסדרה הראשונה מופיע 1 בדיוק 3 פעמים, 2 מופיע פעמיים, וכדומה. ה"גודל" של האיבר הזה הוא סכום הגדלים של ארבעת הסדרות, והגודל שלהן בתורו הוא סכום הגדלים של האיברים שבהם; מכאן שגודל הסדרה הראשונה הוא 3, גודל הסדרה השניה 4, גודל השלישית 7 וגודל הרביעית 26 ולכן הגודל הכולל של האיבר הזה הוא 40. האיבר הזה, כפי שודאי כבר הבנתם, מייצג חלוקה של המספר 40, ובאופן כללי כל איבר בגודל 40 בתוך \(\mbox{MS}\left(\mathbb{N}\right)\) יתאים לחלוקה של המספר 40. לכן כמות האיברים מגודל 40 ב-\(\mbox{MS}\left(\mathbb{N}\right)\) היא בדיוק מספר החלוקות של 40 – בדיוק מה שרצינו.

בואו נחזור שניה להגדרה הפורמלית, רק עבור המתמטיקאים בחבורה – מי שהפסקה הזו מטרללת אותו יכול לדלג, זו פורמליסטיקה חשובה אבל לא קריטית להצגה פופולרית כמו פה. \(\prod_{a\in A}\left\{ a\right\} ^{*}\) היא הגדרה בעייתית אם \(A\) אינסופית, כי אין משמעות, למשל, לאיבר שמתקבל מהמכפלה \(\prod_{a\in A}\left\{ a\right\} \) – זה יהיה איבר מגודל אינסופי. כדי למנוע היווצרות של איברים כאלו צריך להשתמש בתעלול נוסף – נשתמש בסימון \(\prod_{a\in A}^{n}\left\{ a\right\} ^{*}\) כדי לתאר את המכפלה המתאימה שבה משתתפים כל אברי \(A\) עד האיבר שמספרו הסידורי הוא \(n\), תחת איזה סידור מוסכם מראש של אברי \(A\). כעת אפשר להגדיר \(\mbox{MS}\left(A\right)=\sum_{n=1}^{\infty}\prod_{a\in A}^{n}\left\{ a\right\} ^{*}\) – זה משיג בצורה פורמלית את מה שאני מקווה כבר ברור אינטואיטיבית.

עכשיו, נניח שאנחנו יודעים את הפונקציה היוצרת \(a\left(x\right)\) של \(A\); מהי הפונקציה היוצרת של \(\mbox{MS}\left(A\right)\)? כאן העסק מסתבך. ראשית, מה הפונקציה היוצרת של \(\left\{ a\right\} ^{*}\)? על פי מה שראינו בפוסט הקודם, היא \(\frac{1}{1-x^{\left|a\right|}}\) כש-\(\left|a\right|\) הוא הגודל של \(a\); הפונקציה הזו מתאימה לסדרה שכולה 0-ים פרט למקומות שהם כפולות שלמות של הגודל של \(a\) ובהם יש 1. מכאן, אם נלך עם האינטואיטציה של אוילר, שהפונקציה היוצרת שאנו מחפשים היא \(\prod_{a\in A}\frac{1}{1-x^{\left|a\right|}}\), שאותה אפשר לכתוב גם כ-\(\prod_{n=1}^{\infty}\left(\frac{1}{1-x^{_{n}}}\right)^{a_{n}}\), כאשר \(a_{n}\) הוא מספר האיברים מגודל \(n\) ב-\(A\). זו לא דרך הצגה יפה במיוחד כי המקדמים \(a_{n}\) פזורים להם בכל מקום – אנחנו רוצים תיאור שתופיע בו רק הפונקציה \(a\left(x\right)\) עצמה. לשם כך נשתמש בתעלול ידוע שהופך מכפלות לסכומים – שימוש בלוגריתם. כזכור, \(y=\exp\left(\log y\right)\) כאשר \(\exp\left(t\right)\) זו פשוט דרך תרבותית לכתוב \(e^{t}\) בלי לחרוג מהשורה.

אם כן: \(\prod_{n=1}^{\infty}\left(\frac{1}{1-x^{_{n}}}\right)^{a_{n}}=\exp\left(\log\prod_{n=1}^{\infty}\left(\frac{1}{1-x^{_{n}}}\right)^{a_{n}}\right)\), והביטוי הזה מתפשט לו והופך ל:

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

הצעד הבא דורש קצת היכרות עם לוגריתם וזהות סטנדרטית (ושימושית מאוד) מאנליזה: \(\log\left(1-x\right)=-\sum_{n=1}^{\infty}\frac{x^{n}}{n}\). אחרי שימוש בה, מקבלים:

\(\exp\left(\sum_{n=1}^{\infty}a_{n}\sum_{k=1}^{\infty}\frac{\left(x^{n}\right)^{k}}{k}\right)\)

ועכשיו מגיע טריק סטנדרטי נוסף – שינוי סדר הסכימה:

\(\exp\left(\sum_{k=1}^{\infty}\frac{1}{k}\left(\sum_{n=1}^{\infty}a_{n}\left(x^{k}\right)^{n}\right)\right)\)

וכעת הפאנץ' – מהו \(\sum_{n=1}^{\infty}a_{n}\left(x^{k}\right)^{n}\)? ובכן, על פי ההגדרה ממש, זהו \(a\left(x^{k}\right)\). לכן קיבלנו:

\(\exp\left(\sum_{k=1}^{\infty}\frac{a\left(x^{k}\right)}{k}\right)\)

וזוהי הפונקציה היוצרת של \(\mbox{MS}\left(A\right)\).

כן, אמרתי שזה הולך להיות יותר משוגע בהמשך, כן? (עם זאת, זה עדיין חומר בסיסי למדי…)

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

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

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

בואו נשתמש בסימון \(P\left(x\right)=\prod_{n=1}^{\infty}\frac{1}{1-x^{n}}\) (P מלשון Partition – חלוקה), ונסמן ב-\(p_{n}\) את מספר החלוקות של \(n\). כעת ניקח את \(P\left(x\right)\) ונתעלל בה על ידי לקיחת מה שנקרא "נגזרת לוגריתמית" – זה שם מפוצץ לכך שאנחנו מפעילים לוגריתם על \(P\left(x\right)\) וגוזרים את הכל. מה שמקבלים מזה הוא את \(\frac{P^{\prime}\left(x\right)}{P\left(x\right)}\); באגף ימין אחרי הפעלת לוגריתם נקבל \(-\sum_{n=1}^{\infty}\log\left(1-x^{n}\right)\) ואחרי גזירה – \(\sum_{n=1}^{\infty}\frac{nx^{n-1}}{1-x^{n}}\). נכפול את שני האגפים ב-\(x\) וקיבלנו את השוויון:

\(x\frac{P^{\prime}\left(x\right)}{P\left(x\right)}=\sum_{n=1}^{\infty}\frac{nx^{n}}{1-x^{n}}\)

כעת נכפול ב-\(P\left(x\right)\) את שני האגפים, וקיבלנו \(xP^{\prime}\left(x\right)=P\left(x\right)\cdot\sum_{n=1}^{\infty}\frac{nx^{n}}{1-x^{n}}\). במבט ראשון הנוסחה הזו מעוררת בי רצון לפרוץ בבכי, אבל היא באמת לא נוראה עד כדי כך: אגף שמאל הוא \(\sum_{n=1}^{\infty}np_{n}x^{n}\) (למה? ובכן, \(P\left(x\right)=\sum_{n=0}^{\infty}p_{n}x^{n}\) – מה קורה כשגוזרים איבר-איבר וכופלים ב-\(x\)?). מה שהולך באגף ימין כואב קצת יותר, בכלל ה-\(\frac{1}{1-x^{n}}\) שיש שם. מה שצריך לעשות הוא להשתמש בזהות \(\frac{1}{1-x^{n}}=\sum_{k=0}^{\infty}x^{nk}\), ואז מקבלים שאגף ימין הוא

\(P\left(x\right)\cdot\sum_{n=1}^{\infty}n\left(\sum_{k=1}^{\infty}x^{nk}\right)=\sum_{k=1}^{\infty}\left(\sum_{n=1}^{\infty}nx^{nk}\right)\)

את הכפל הזה אפשר לבצע על פי חוקי הכפל הרגילים של טורי חזקות. אנחנו רוצים לדעת מהו המקדם של \(x^{n}\); אז לכל \(j\) מ-\(1\) ועד \(n\), נניח ש-\(P\left(x\right)\) תורם את האיבר \(p_{n-j}x^{n-j}\) למכפלה ונותר להבין מה המקדם של \(x^{j}\) בטור הימני. בכל פעם שבה \(x^{j}\) מתקבל זה באמצעות מכפלה מהצורה \(j=nk\), כלומר \(n\) מחלק את \(j\); ועבור \(n\) הזה הערך שנתרם לסכום של המקדם הוא בדיוק \(n\). השורה התחתונה – המקדם של \(j\) יהיה בדיוק \(\sigma\left(j\right)\) – סכום המחלקים של \(j\) (כולל \(j\) עצמו). זו פונקציה מוכרת וחשובה בזכות עצמה.

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

\(np_{n}=\sum_{j=1}^{\infty}\sigma\left(j\right)p_{n-j}\)

זו נוסחה רקורסיבית שמאפשרת חישוב יעיל למדי של \(p_{n}\) (פורמלית, הסיבוכיות היא \(O\left(n^{2}\right)\) לחישוב כל הערכים \(p_{1},\dots,p_{n}\)). והנוסחה הזו (שלדעתי היא אלגנטית למדי) הופקה באמצעות הפונקציה היוצרת \(P\left(x\right)\); זו המחשה לסוג הדברים שאפשר להפיק מפונקציות יוצרות בעולם האמיתי (וכפי שאנו רואים, זה לא קל לעיכול מיידי – אף שאין כאן מתמטיקה מחוכמת במיוחד).

אני רוצה לעבור עכשיו לדבר על סוג אחר של פונקציות יוצרות – פונקציות יוצרות אקספוננציאליות. הפונקציות היוצרות ה"רגילות" שבהן השתמשנו עד כה תופסות היטב מבנים לא מסומנים. כך למשל בחלוקות, \(3=1+1+1\) אבל כל ה"1"-ים הללו זהים, ולכן \(1+2=3\) נספר רק פעם אחת ולא שלוש פעמים (אם היה לנו "1 ירוק", "1 אדום" ו"1 כחול" היינו צריכים לספור את \(1+2=3\) לכל אחד משלושת צבעי ה-1-ים הללו). אולי הדוגמה הפשוטה ביותר לבעיה שעוסקת באיברים מסומנים היא תמורה שלהם – סידור של \(n\) המספרים מ-1 ועד \(n\) בשורה. אולי התוצאה הבסיסית ביותר שנלמדת בקומבינטוריקה הוא שמספר הסידורים הוא \(n!\), כך שהפונקציה היוצרת המתאימה היא \(\sum_{n=0}^{\infty}n!x^{n}\). זו פונקציה יוצרת בעייתית למדי; אם מנסים לחשוב עליה כעל אובייקט אנליטי ולא רק פורמלי, אז לא משנה איזה ערך נציב ב-\(x\) (מתוך המרוכבים), הטור הזה יתכנס רק עבור \(x=0\). אז במקום להסתבך עם פונקציות כאלו, "מנרמלים".

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

כמו במקרה של פונקציות יוצרות רגילות, כך גם כאן פעולות אלגבריות על הפונקציות היוצרות הן בעלות משמעות קומבינטורית. חיבור הוא בעל משמעות של איחוד זר, כמקודם; אבל כפל הוא בעל משמעות קצת שונה, שהיא זו שמאפשרת לנו לחשוב על הפונקציות היוצרות האקספוננציאליות בתור ייצוגים טובים ל"מבנים מסומנים". מכפלה היא אוסף של זוגות, כמקודם, אבל כל זוג מתקבל כך: בהינתן \(x\in X\) ו-\(y\in Y\) שהאטומים שלהם מסומנים (נוח לחשוב על \(x,y\) תמיד בתור גרפים עם סימונים לצמתים), בונים מהם את כל הזוגות האפשריים \(\left(x^{\prime},y^{\prime}\right)\) שבהם יש סימון כלשהו שעונה לדרישה שאם מסתכלים רק על הסימונים של \(x^{\prime}\) הם איזומורפיים לאלו של \(x\) מבחינת הסדר ביניהם, וכך גם עבור \(y^{\prime}\) (בנוסף גם דורשים שהמספרים יהיו בטווח \(1,\dots,n\) כאשר \(n\) הוא הגודל הכולל של הזוג; אחרת יווצרו לנו אינסוף זוגות כך עבור \(\left(x,y\right)\)). גם זה מבלבל קצת במבט ראשון אבל לא יהיה קריטי בהמשך.

בואו נגדיר עוד פעולה אחת ואז ניתן דוגמת מחץ. אם \(A\) היא מחלקה, נגדיר \(\mbox{SET}\left(A\right)\) בתור אוסף כל תת הקבוצות הסופיות של איברים מ-\(A\) (אם \(A\) היא מחלקה של גרפים, אז \(\mbox{SET}\left(A\right)\) היא מחלקה של קבוצות סופיות של גרפים). זו פעולה קצת יותר פשוטה מאשר \(\mbox{MS}\) של המקרה הלא מסומן, כי במקרה הלא מסומן היה צריך להתמודד איכשהו עם "אותו איבר שמופיע כמה פעמים" וכאן, בגלל שלכל איבר יש סימון ייחודי, זה לא קורה.

אם נסמן ב-\(\mbox{SET}_{k}\left(A\right)\) את אוסף כל הקבוצות מגודל \(k\) של איברים ב-\(A\), את הפונקציה היוצרת של זה קל למצוא בעזרת הלהטוט הבא: אם נספור את כל הסדרות מגודל \(k\), זה יהיה בדיוק \(A^{k}\) (חזקה מוגדרת כמו קודם); מכיוון שאין חשיבות לסדר, ויש \(k!\) סידורים שונים לסדרה מאורך \(k\), נקבל שהפונקציה היוצרת המתאימה היא \(\frac{a^{k}\left(x\right)}{k!}\) (אם זה מהיר לכם מדי, תנסו להוכיח זאת לעצמכם). עכשיו אפשר לקבל את \(\mbox{SET}\left(A\right)\) מייד מכך ש-\(\mbox{SET}\left(A\right)=\bigcup_{k=0}^{\infty}A^{k}\): הפונקציה היוצרת תהיה בדיוק \(\sum_{k=0}^{\infty}\frac{a^{k}\left(x\right)}{k!}\), ואת זה מסמנים באופן קומפקטי בתור \(\exp\left(a\left(x\right)\right)\).

בואו נעבור סוף סוף לדוגמה שלטעמי היא מרשימה למדי – עצים מסומנים עם "שורש". שורש הוא פשוט צומת שנבדל מכל היתר בכך שפרט למספר שלו, הוא גם נקרא "שורש" (יש להבדלה הזו שימושים רבים שלא אכנס אליהם). נסמן ב-\(T\) את המחלקה וב-\(T\left(x\right)\) את הפונקציה היוצרת המתאימה. ב-\(A\) אסמן שוב, כמו בפוסט הקודם, מחלקה בעלת איבר בודד. אז הפאנץ' הוא ש-\(T\) מקיימת את המשוואה הבאה: \(T=A\times\mbox{SET}\left(T\right)\) (הכפל הוא על פי ההגדרה החדשה שנתתי).

למה? ובכן, ממה מורכב עץ סופי עם שורש? מהשורש (זה \(A\)), כשאליו מצורף מספר סופי כלשהו של עצים (כולם מסומנים) – זה \(\mbox{SET}\left(T\right)\). השימוש בקבוצה מבהיר שאין חשיבות ל"סדר" שבו תת העצים מחוברים אל השורש (להבדיל ממה שעשינו בפוסט הקודם). זה מניב את הנוסחה הבאה עבור הפונקציה היוצרת: \(T\left(x\right)=x\cdot e^{T\left(x\right)}\), ולכאורה נתקענו – אין דרך להגיע לייצוג סגור ל-\(T\left(x\right)\) מהנוסחה האלגנטית-אך-מוזרה הזו. אז האם צריך להתייאש?

לא! מטרת הפוסט הזה היא בראש ובראשונה להראות שאפילו ממשהו שאיננו צורה סגורה אפשר לחלץ מידע קריטי. השפן שאנחנו שולפים עכשיו מהכובע הוא תוצאה באנליזה של לגראנז' ("נוסחת ההיפוך של לגראנז'") שעובדת גם בהקשר הפורמליסטי שלנו. אציג את הניסוח ה"קומבינטורי" שלה (הניסוח הכללי מורכב קצת יותר).

נניח שיש לנו טור חזקות \(\phi\left(u\right)=\sum_{k=0}^{\infty}\phi_{k}u^{k}\), ונניח גם ש-\(\phi_{0}\ne0\), מה שמבטיח שקיים הופכי ל-\(\phi\). עכשיו, הבה ונתבונן במשוואה \(f\left(x\right)=x\phi\left(f\left(x\right)\right)\); קיים לה פתרון יחיד, \(f\left(x\right)=\sum_{n=1}^{\infty}a_{n}x^{n}\). לצורך נוחות הסימון, אני אשתמש ב-\(\left[x^{n}\right]f\left(x\right)\) כדי להגיד "המקדם של \(x^{n}\) ב-\(f\left(x\right)\) (כלומר, \(a_{n}\)) וכך גם עבור \(\phi\) אשתמש בסימון דומה. מה שנוסחת ההיפוך של לגראנז' נותנת לנו הוא המקדמים של \(f\left(x\right)\):

\(\left[x^{n}\right]f\left(x\right)=\frac{1}{n}\left[u^{n-1}\right]\phi\left(u\right)^{n}\).

לפני שתאבדו אותי סופית, נראה איך זה עוזר לנו במקרה של \(T\left(x\right)=xe^{T\left(x\right)}\). כאן בבירור \(\phi\left(u\right)=e^{u}\) וזו, למזלנו, פונקציה פשוטה למדי. לכן נקבל:

\(\left[x^{n}\right]T\left(x\right)=\frac{1}{n}\left[u^{n-1}\right]e^{un}=\frac{1}{n}\cdot\frac{n^{n-1}}{\left(n-1\right)!}=\frac{n^{n-1}}{n!}\)

זה המקדם של \(T\left(x\right)\); ומכיוון ש-\(T\left(x\right)\) הוא פונקציה יוצרת אקספוננציאלית, יש להכפיל את המקדם ב-\(n!\) כדי לקבל את המספר האמיתי – \(n^{n-1}\) הוא מספר העצים המסומנים עם שורש. מכיוון שיש \(n\) בחירות אפשריות לשורש, אז על ידי חלוקה ב-\(n\) אנו מקבלים ש-\(n^{n-2}\) הוא מספר העצים המסומנים בכלל – וזו תוצאה מפורסמת למדי בקומבינטוריקה – משפט קיילי. לתוצאה יש הוכחות קומבינטוריות מקסימות, אבל העובדה שהיא מתקבלת מיידית כמעט מכלים סטנדרטיים בפונקציות יוצרות היא מרשימה מאוד לדעתי. כמובן שהסיפור לא נגמר כאן ושלל של תוצאות בעלות אופי דומה למשפט קיילי יכול להתקבל גם כן בעזרת טכניקות דומות.

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

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

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

אוקיי, ולמה כשיש שישה אנשים זה כן עובד? נתחיל שוב מצ'נדלר. יש לו חמישה חברים שמשתתפים במשחק, ולכן לפחות שלושה מהם שונאים אותו, או שלפחות שלושה מהם אוהבים אותו (הפעם זה לא בדיוק "או" מתמטי – במובהק רק אחת משתי האפשרויות תתרחש) – זו דוגמה נאה לשימוש בעקרון שובך היונים הכללי יותר שאומר שאם מחלקים \(n\) עצמים ל-\(m\) תאים יש בהכרח תא שמכיל לפחות \(\left\lceil \frac{n}{m}\right\rceil \) עצמים (הסימון הזה הוא לערך שלם עליון – המספר הטבעי הקרוב ביותר מלמעלה ל-\(\frac{n}{m}\)).

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

התרגיל הבא בתור הוא להראות שאם יש 9 אנשים, אז מובטח שתהיה שלישיית שונאים או רביעיית אוהבים (או לחילופין, תהיה שלישיית אוהבים או רביעיית שונאים – הסבירו לעצמכם למה זה לא אותו דבר כמו לומר שתהיה רביעיית אוהבים או רביעיית שונאים, מה שדורש כבר 18 אנשים), ונראה לי שהעיקרון כבר ברור. השאלה שאנו שואלים את עצמנו היא – האם זה תמיד עובד? האם לכל \(r,s\) קיים מספר חברים, שנסמן \(R\left(r,s\right)\), כך שבקבוצה עם לפחות \(R\left(r,s\right)\) אנשים מובטחת לנו קבוצה של \(r\) אוהבים או קבוצה של \(s\) שונאים? משפט רמזי אומר שהתשובה חיובית בכך שהוא נותן חסם עליון על \(R\left(r,s\right)\) לכל \(r,s\). מה שדיברנו עליו בתחילת הפוסט הוא בדיוק המקרה של \(R\left(3,3\right)\) וראינו כי \(R\left(3,3\right)=6\).

ההוכחה של המשפט היא באינדוקציה, ואינדוקציה קצת יותר מחוכמת מהרגיל במובן זה שהיא "דו ממדית". ראשית שמים לב לכך ש-\(R\left(1,s\right)=R\left(r,1\right)=1\) תמיד, באופן די טיפשי – קבוצה של אדם בודד היא תמיד קבוצה של אוהבים/שונאים "באופן ריק". למי שזה נשמע לו לא הגיוני בעליל, תחשבו על זה כך – קבוצת אנשים היא קבוצה של אוהבים או שונאים כל עוד לא הוכח אחרת; כדי להוכיח שקבוצה איננה קבוצת אוהבים צריך להביא זוג שונאים בתוכה, וכדי להוכיח שהיא לא קבוצת שונאים צריך להביא זוג אוהבים בתוכה. בקבוצה בעלת אדם אחד אי אפשר להביא זוג שכזה ממילא, ולכן הקבוצה נחשבת הן לקבוצת אוהבים והן לקבוצת שונאים בו זמנית. כן, זה מוזר וקשה לעיכול למדי למי שטרם נתקל בשיקולים שכאלו, אבל במתמטיקה הם נפוצים למדי ותקינים לחלוטין.

השלב הבא באינדוקציה הוא זה: אנחנו רוצים למצוא חסם עליון על \(R\left(r,s\right)\) בהינתן שאנחנו כבר יודעים חסמים עליונים על \(R\left(r-1,s\right)\) ו-\(R\left(r,s-1\right)\). החסם העליון יהיה פשוט למדי – נוכיח שמתקיים \(R\left(r,s\right)\le R\left(r-1,s\right)+R\left(r,s-1\right)\), וחסל.

אם כן, הבה ונתבונן על קבוצה בעלת \(R\left(r,s\right)\) אנשים. ניקח איש אחד, נקרא לו צ'נדלר, ונחלק את שאר האנשים לשתי קבוצות – חברי צ'נדר ואויבי צ'נדלר. אני מניח שאתם מבינים לאן אני הולך – הפתרון של המקרה הכללי יהיה הכללה פשוטה של המקרה של \(R\left(3,3\right)\). מה שאנחנו רוצים לראות הוא שיש לצ'נדלר מספיק חברים או מספיק אויבים כדי להפעיל אחת מהנחות האינדוקציה.

אם לצ'נדלר יש לפחות \(R\left(r-1,s\right)\) חברים, סיימנו – בקבוצה הזו או שיש \(s\) אויבים (ואז סיימנו) או שיש בה \(r-1\) חברים ואז יחד עם צ'נדלר נקבל קבוצה של \(r\) חברים וסיימנו. בדומה, אם יש לו לפחות \(R\left(r,s-1\right)\) אויבים סיימנו באותו האופן. למה לא ייתכן שאין לו לא מספיק חברים ולא מספיק אויבים?

כדי לא להתבלבל נכניס עוד כמה סימונים למשחק. \(A\) יהיה מספר החברים של צ'נדלר, \(B\) יהיה מספר האויבים שלנו, וראינו ש-\(A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right)\) (הפלוס 1 הוא כי גם את צ'נדלר סופרים). אז אם \(A<R\left(r-1,s\right)\) וגם \(B<R\left(r,s-1\right)\) זה אומר ש-\(A+B\le R\left(r-1,s\right)+R\left(r,s-1\right)-2\), כלומר שלא ייתכן ש-\(A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right)\) (למי שעדיין לא רואה את זה, \(a<b\) שקול לאמירה ש-\(a\le b-1\) אם \(a,b\) הם טבעיים; זו אבחנה מועילה מאוד לעתים).

זה מסיים את ההוכחה; עוד הרחבה לא מסובכת מטפלת במקרה יותר כללי, שבו זוג אנשים יכול להיות יותר מסתם חברים או אויבים, אלא יש \(s\) סוגים שונים אפשריים של קשרים ביניהם – ושוב, אפשר להראות שלכל סדרת מספרים \(r_{1},r_{1},\dots,r_{s}\) קיימת כמות אנשים שהחל ממנה, מובטח שעבור \(i\) כלשהו יש קבוצה של \(r_{i}\) אנשים שהקשרים ביניהם הם רק מסוג \(i\). בניסוח אינטואיטיבי יותר ופחות פורמלי – במבנים גדולים מספיק חייבות לצוץ תבניות מסויימות (זה, על רגל אחת, הרעיון של תורת רמזי; משפט רמזי מטפל בסוג ספציפי של תבניות – בלשון מתמטית, הוא מטפל בתת-גרפים מונוכרומטיים של גרף עם קשתות צבועות).

לסיום, הנה שאלה קטנה וחביבה. ראינו ש-\(R\left(3,3\right)=6\), כלומר שאם יש 6 אנשים מובטחת לנו שלישיית חברים או שלישיית שונאים, וש-5 אנשים אינם מספיקים. אפשר להראות גם ש-\(R\left(4,4\right)=18\). אם כן, מהו \(R\left(5,5\right)\)?

באופן מפתיע למדי, ממבט ראשון, התשובה אינה ידועה עד היום. משפט רמזי אמנם נותן חסם עליון פשוט על \(R\left(5,5\right)\), אבל לא עוזר למצוא את הערך המדויק שלו. בדי עמל הצליחו המתמטיקאים להראות ש-\(43\le R\left(5,5\right)\le49\), אבל זהו זה. הרי לכם בעיה פתוחה במתמטיקה שתיאוריה הוא אלמנטרי דיו כדי להיות מוסבר בפוסט קצר. אתם עשויים לתהות מה הקושי הגדול כל כך – האם לא ניתן לגייס מחשבים לעבודה ולעשות חיפוש ממצה כלשהו? נאמר, ניקח את כל הקבוצות האפשריות של יחסי אהבה/שנאה על 43 אנשים ונבדוק לכל אחת… כן, ובכן, תשכחו מזה. אם יש לנו 43 אנשים אז יש לנו \(\frac{43\cdot42}{2}=903\) זוגות בסך הכל. לכל אחד מהם אנחנו יכולים לבחור, באופן בלתי תלוי באחרים, ביחס אהבה/שנאה, כך שיש לנו כבר \(2^{903}\) קבוצות אפשריות. המספר \(2^{903}\) הוא גדול. ממש, ממש גדול. כמה גדול? גדול להחריד גם בהשוואה למספרים הגדולים שדיברתי עליהם בפוסט הזה. אז חיפוש ממצה הוא כיוון אבוד לחלוטין; הכרחי יהיה לעשות הרבה עבודת הכנה מתמטית תיאורטית כדי שתהיה תקווה להריץ איזה חיפוש מחשב שגם יתן את התוצאה הנכונה. ונניח שנצליח, האתגר הבא יהיה מציאת \(R\left(6,6\right)\). כדי להבין עד כמה הקפיצה הזו בקושי בין \(R\left(5,5\right)\) ו-\(R\left(6,6\right)\) תהיה משמעותית כדאי לתת את הבמה לרגע לג'ואל ספנסר שמצטט את ארדש:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, he believes, we should attempt to destroy the aliens.

הציטוט הנפלא הזה לבדו שווה את כל הפוסט.

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

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

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

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

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

נעבור לבחירה בלי החזרה אך עם חשיבות לסדר, מה שנקרא לעתים בעברית "חליפות"ומסומן ב-\(A_{n}^{k}\). הדרך לחשב את מספר האפשרויות לבחור בלי החזרה ועם חשיבות לסדר \(k\) מתוך \(n\) עצמים היא פשוטה למדי כי אפשר לחשוב עליה כתהליך דו-שלבי: קודם כל נבחר \(k\) עצמים מתוך ה-\(n\) בלי חשיבות לסדר, ואז נבחר את האופן שבו "מסדרים"אותם. כבר ראינו שיש \({n \choose k}\) אפשרויות לבחור את העצמים בלי חשיבות לסדר, ושבהינתן \(k\) עצמים יש \(k!\) דרכים לסדר אותם, כך שהתוצאה היא \({n \choose k}k!=\frac{n!}{k!\left(n-k\right)!}k!=\frac{n!}{\left(n-k\right)!}\). אפשר גם להגיע לתוצאה הזו בדרך ישירה: בהתחלה יש לנו \(n\) איברים לבחור מהם, אחר כך יש לנו \(n-1\) איברים, אחר כך \(n-2\) וכן הלאה… עד שבסופו של דבר יש לנו \(n-k\) איברים ואז אנחנו כבר לא בוחרים. נקבל את המכפלה \(n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdots\left(n-k+1\right)\) (ה-\(+1\) בסוגר האחרון נובע מכך שהבחירה האחרונה מתבצעת רגע לפני שאנו נשארים עם \(n-k\) איברים) – לא קשה לראות שמכפלה זו אכן שווה ל-\(\frac{n!}{\left(n-k\right)!}\), אבל היא יותר מסורבלת לכתיבה. שימו לב, אגב, שאם היינו בוחרים \(k=n\) היינו מקבלים את התוצאה \(n!\) – כלומר, הכללנו גם את הרעיון של סידור \(n\) איברים בשורה.

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

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

טוב, אז זה מסיים את עניין הבחירה בלי החזרות. הבה ונעבור לבחירה עם החזרות – שימו לב שכאן \(k\) יכול להיות גדול מ-\(n\) כי האיברים לא יכולים "להיגמר" לנו. הסיטואציה כאן מאוד מעניינת – מצד אחד, אם יש חשיבות לסדר הנוסחה פשוטה ביותר (כה פשוטה שאני ממליץ לכם לנסות ולהמציא אותה לבד לפני שתקראו מה שאכתוב). מצד שני, הנוסחה עבור בחירה עם החזרות אך בלי חשיבות לסדר היא קשה יחסית – כה קשה שאיני חושב שמלמדים אותה כלל בתיכון, אפילו אם כן לומדים קומבינטוריקה. למרות זאת הדגש צריך להיות על הקושי היחסי: הנוסחה אינה נוראית כלל ואני מקווה שעד סיום הפוסט יוכלו כל הקוראים לפתח אותה בעצמם.

הנוסחה לבחירה עם החזרה ועם חשיבות לסדר היא תוצאה ישירה של עקרון הכפל. תהליך הבחירה שלנו הוא בן \(k\) שלבים; בכל שלב אנחנו בוחרים אחת מ-\(n\) אפשרויות שונות. יש לנו אם כן בסך הכל \(n\cdot n\cdots n=n^{k}\) אפשרויות שונות. קל להתבלבל ולשכוח מי במעריך החזקה ומי בבסיס (כלומר, האם זה \(k^{n}\) או \(n^{k}\)) ולכן אני ממליץ לנקוט בגישה הבאה: כמה מספרים דו ספרתיים יש, אם מרשים גם לאפס להופיע (כלומר, \(3\) הוא המספר ה"דו ספרתי" \(03\) וכדומה)? \(2^{10}\) או \(10^{2}\)? ובכן, \(2^{10}=1024\) כך שברור שיש כאן בעיה; לעומת זאת \(10^{2}\) מתאים בדיוק, וזה לא מפתיע כי מספר דו ספרתי מורכב מבחירה של אחת מ-10 הספרות האפשריות בתור ספרת האחדות, ואחת מ-10 הספרות האפשריות בתור ספרת העשרות.

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

הדרך הנוחה ביותר לתאר זאת היא באמצעות סיפור מעשיות. בחירה של \(k\) מתוך \(n\) איברים ללא חשיבות לסדר ועם החזרה ניתן לתאר בתור סידור כדורים בתאים: נניח שיש לנו שורה של \(n\) תאים ממוספרים, ו-\(k\) כדורים זהים. אנחנו זורקים כדורים לתוך התאים ובסוף רואים מה קיבלנו. אם בתא מס' 1 יש שני כדורים, אנחנו אומרים שבחרנו את האיבר מס' 1 בדיוק שתי פעמים; אם בתא 2 אין כדורים כלל אנו אומרים שאת איבר מס' 2 בכלל לא בחרנו, וכן הלאה.

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

בגישה הזו מה שאני "בוחר" הוא את המקומות שבהם אני רוצה לשים את המחיצות. על פניו כל רווח בין שני כדורים, או בין כדור והקיר, הוא מיקום חוקי. יש \(k\) כדורים ולכן \(k+1\) רווחים (ציירו שני כדורים ותראו את שלושת הרווחים: מימין לכדור הימני, משמאל לשמאלי, ובין שניהם). לכן יש לי בחירה של \(n-1\) איברים מתוך קבוצה של \(k+1\) איברים, בלי חשיבות לסדר ועם החזרה, כי אפשר לבחור באותו רווח כמה פעמים… היי, רגע, אז מה בעצם השגתי כאן? אני עדיין תקוע עם בעיה של בחירה עם החזרה ולא שיפרתי כלום!

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

הטענה שלי היא כזו: מספר הדרכים השונות לחלק \(k\) כדורים ל-\(n\) תאים (בלי חשיבות לסדר) שווה בדיוק למספר הדרכים השונות לחלק \(n+k\) כדורים ל-\(n\) תאים כשבסוף החלוקה אין תאים ריקים. למה? זה פשוט: כי נתחיל את החלוקה בלשים כדור אחד בכל תא. כך הבטחנו שמה שחייב להתקיים, מתקיים, ואז \(k\) הכדורים שנותרו אפשר לחלק בשקט ובלי מגבלות כלשהן. אם כן, המרנו את הבעיה שלנו לבעיה אחרת, שאותה יהיה לנו קל יותר לתקוף.

נחזור לבעיית השמת המחיצות. אם אסור שיהיו תאים ריקים, זה אומר שאסור לשים שתי מחיצות בין אותו זוג כדורים, ואסור לשים מחיצה בין כדור ובין הקיר. מצד שני, יש לנו הפעם \(n+k\) כדורים, ולכן יש בסך הכל \(n+k-1\) רווחים שבהם ניתן לשים את \(n-1\) המחיצות. הפעם הבחירה היא בלי החזרות כי כאמור, אסור לשים שתי מחיצות בין אותו זוג כדורים – אסור לבחור פעמיים באותו רווח שבין כדורים. לכן יש לנו בחירה של \(n-1\) איברים מתוך \(n+k-1\) איברים, וזה בדיוק \({n+k-1 \choose n-1}\), ואת זה ניתן לכתוב גם כ-\({n+k-1 \choose k}\). בזאת מצאנו את הנוסחה לשיטת החלוקה הרביעית והאחרונה.

לפני שנסיים להפעם אני רוצה לתאר שימוש פשוט אחד בבחירה עם החזרה ובלי חשיבות לסדר, שבינתיים אולי נראית מפחידה ומסובכת ולא מועילה כלל. נביט במשוואה \(x_{1}+x_{2}+\dots+x_{n}=k\), כאשר \(k\) הוא מספר שלם והערכים שאנחנו מרשים למשתנים לקבל הם רק ערכים שלמים אי שליליים (משוואות כאלו צצות בפועל! בעולם האמיתי! תאמינו לי!). כמה פתרונות יש למשוואה הזו? בדיוק מספר האפשרויות לבחור \(k\) איברים מתוך \(n\), עם החזרה ובלי חשיבות לסדר. למה? אשאיר זאת כתרגיל לקורא.