פונקציות יוצרות - והפעם ברצינות (חלק ב')

אני רוצה להמשיך לדבר על פונקציות יוצרות והדברים המגניבים שעושים איתן, ובפוסט הזה ללכת לכיוונים עוד יותר טכניים מהפוסט הקודם (כי ככה זה במתמטיקה - כשמגיעים לדברים מתוחכמים, זה גם נהיה יותר טכני). בפוסט הקודם ראינו כי אם \( 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} \) הוא מספר העצים המסומנים בכלל - וזו תוצאה מפורסמת למדי בקומבינטוריקה - משפט קיילי. לתוצאה יש הוכחות קומבינטוריות מקסימות, אבל העובדה שהיא מתקבלת מיידית כמעט מכלים סטנדרטיים בפונקציות יוצרות היא מרשימה מאוד לדעתי. כמובן שהסיפור לא נגמר כאן ושלל של תוצאות בעלות אופי דומה למשפט קיילי יכול להתקבל גם כן בעזרת טכניקות דומות.

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