פונקציות יוצרות - והפעם ברצינות

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

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

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

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

אם כן, לפעמים צריך גישה שונה לגמרי לבעיות קומבינטוריות ופונקציות יוצרות מציעות גישה שונה לגמרי שכזו. בעוד שנוסחה סגורה עבור \( a_{n} \) מתארת איבר בודד בסדרה, פונקציה יוצרת היא דרך לתאר את כל הסדרה (האינסופית!) “בבת אחת”.

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

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

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

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

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

\( c\left(x\right)=a\left(x\right)+b\left(x\right) \) אם \( c_{n}=a_{n}+b_{n} \); זהו חיבור טבעי “איבר איבר”.

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

מה שצריך לשים לב אליו כאן הוא שלמרות ששני טורי החזקות הם אינסופיים, כל מקדם \( c_{n} \) נקבע באמצעות כמות סופית של איברים, כלומר \( c\left(x\right) \) מוגדר היטב בלי להיכנס בכלל לשאלות של התכנסות של טורים אינסופיים. זה בדיוק מה שמאפשר לנו להישאר פורמליים מבלי לגלוש לאנליזה.

בואו נעבור לדוגמה - הסדרה \( 1,1,1,\dots \). האם יש משהו (אינסופי) פשוט מזה? הפונקציה היוצרת המתאימה היא \( 1+x+x^{2}+x^{3}+\dots=\frac{1}{1-x} \). איך הגעתי לכך שאגף שמאל שווה ל-\( \frac{1}{1-x} \) אתם שואלים? אה, בקלות - סכום של טור הנדסי! אבל, אתם צועקים עכשיו, טור הנדסי אינסופי מתכנס רק כש-\( \left|x\right|<1 \), ובכלל מה הולך כאן, אמרת שלא מדברים על התכנסות!

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

אם כן, הבה ונסמן \( \sum_{n=0}^{\infty}c_{n}=\left(1-x\right)\cdot\sum_{n=0}^{\infty}x^{n} \). מהו \( c_{0} \)? על פי הגדרה, \( c_{0}=a_{0}b_{0}=1\cdot1=1 \). יופי, ומהו \( c_{1} \)? על פי הגדרה, \( c_{1}=a_{0}b_{1}+a_{1}b_{0}=1\cdot1-1\cdot1=0 \). ומה יהיה \( c_{2} \)…?

קל לראות ש-\( c_{n} \), לכל \( n\ge1 \), יהיה אפס, כי תמיד נקבל \( c_{n}=a_{0}b_{n}+a_{1}b_{n-1} \) (כל שאר ה-\( a_{i} \)-ים מתאפסים) ומכיוון שכל ה-\( b_{i} \)-ים הם תמיד 1 ו-\( a_{0}=1,a_{1}=-1 \) נקבל תמיד אפס. מכאן שקיבלנו את השוויון \( \sum_{n=0}^{\infty}x^{n}=\frac{1}{1-x} \) בצורה הכי פורמלית שרק אפשר (כל עוד זוכרים לחשוב על ביטוי מהצורה \( \frac{1}{f\left(x\right)} \) בתור “הפונקציה ההופכית של \( f\left(x\right) \); זו שכשכופלים אותה ב-\( f\left(x\right) \) מקבלים 1”; זה תרגיל נחמד להראות שלטור חזקות כלשהו קיימת פונקציה הופכית אם ורק אם המקדם הראשון בו שונה מאפס).

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

נניח ש-\( A,B \) הם קבוצות של אובייקטים. \( a_{n} \) הוא מספר האובייקטים מגודל \( n \) ב-\( A \) ו-\( b_{n} \) הוא מספר האובייקטים מגודל \( n \) ב-\( B \), ו-\( a\left(x\right),b\left(x\right) \) הפונקציות היוצרות המתאימות. מה מתאר \( a\left(x\right)+b\left(x\right) \)? ובכן, את הפונקציה היוצרת של \( A\cup B \) (הקבוצה שמכילה את כל האיברים של \( A \) וגם את כל האיברים של \( B \)), בתנאי ש-\( A,B \) זרות, כלומר ללא איברים משותפים (כי אחרת איבר משותף היה מופיע רק פעם אחת ב-\( A\cup B \) אבל נספר פעמיים). בשביל שהסימונים יישארו פשוטים אני אסמן ב-\( A+B \) תמיד את האיחוד \( A\cup B \) תחת ההסכמה שאם יש ב-\( A,B \) איברים זהים, כל אחד מהם זוכה לאיזה סימון ייחודי שמבדיל אותו כך שהאיחוד הוא תמיד זר (תרגיל - איך עושים כזה תעלול פורמלית?)

ומה מתאר \( a\left(x\right)\cdot b\left(x\right) \)? או, עכשיו זה נהיה כיפי. הוא מתאר את \( A\times B \) - אוסף הזוגות של איבר מ-\( A \) ואיבר מ-\( B \), אבל יש טוויסט כלשהו - בעצם בנינו כאן סוג חדש של אובייקטים - אובייקטים שהם זוגות, ולכן צריך להגדיר עבורם מושג חדש של “גודל”. ההגדרה מתבקשת: הגודל של האיבר \( \left(a,b\right) \), כש-\( a\in A \) ו-\( b\in B \) הם איברים כלשהם (ממש לא בהכרח מאותו הגודל) הוא פשוט הגודל של \( a \) ועוד הגודל של \( b \). לא קשה לראות ש-\( a\left(x\right)\cdot b\left(x\right) \) אכן מתאר את הפונקציה היוצרת של \( A\times B \) תחת ההגדרה הזו.

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

כעת נגדיר את הפעולה הבאה: \( A^{*}=\bigcup_{n=0}^{\infty}A^{n} \). דהיינו, \( A^{*} \) מכילה סדרות מכל גודל סופי שהוא של איברי \( A \). נניח ש-\( a\left(x\right) \) היא הפונקציה היוצרת של \( A \); אז הפונקציה היוצרת של \( A^{*} \) היא - הפתעה הפתעה - \( \frac{1}{1-a\left(x\right)} \). קרוב לודאי שחלקכם צועקים כרגע “הא! תפסנו אותך! מה אם \( a\left(x\right)=1 \) ותו לא?” ואתם צודקים - הבניה \( A^{*} \) היא בעייתית אם \( A \) מכיל איבר כלשהו מגודל 0, שכן אז הדרישה שלנו שלכל \( n \) יהיה רק מספר סופי של איברים מגודל \( n \) הולכת לפח (למשל, אם \( \alpha \) הוא איבר ב-\( A \) מגודל 0, ו-\( \gamma \) הוא איבר מגודל \( n \), אז אינסוף איברים ב-\( A^{*} \) שכולם מגודל \( n \) הם כל האיברים מהצורה \( \left(\gamma,\alpha,\alpha,\dots\alpha\right) \)), לכן עבור קבוצות \( A \) שכאלו ממילא אין משמעות קומבינטורית סבירה ל-\( A^{*} \); אבל לכל קבוצה אחרת \( \frac{1}{1-a\left(x\right)} \) מוגדר היטב. למה זה מה שיוצא? ובכן, מכללי החיבור והכפל שכבר הראיתי ברור שהפונקציה היוצרת של \( A^{*} \) היא \( 1+a\left(x\right)+a^{2}\left(x\right)+\dots=\frac{1}{1-a\left(x\right)} \).

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

נגדיר \( A=\left\{ 0,1\right\} \) כשהגודל של 0,1 הוא 1. מיידי לראות ש-\( A^{*} \) היא בדיוק המחלקה שאנחנו מעוניינים בה (\( \varepsilon \) מתפרש כאן כסדרה חסרת איברים). מה הפונקציה היוצרת של \( A \)? פשוט מאוד, \( a\left(x\right)=2x \) (שני איברים מגודל 1 ותו לא). מכאן שהפונקציה היוצרת שאנחנו רוצים היא \( \frac{1}{1-2x} \), סוף הסיפור. זו גם פונקציה יוצרת שקל לפתח חזרה לטור חזקות כדי לקבל נוסחה מפורשת למקדמים: \( \sum\left(2x\right)^{n}=\sum2^{n}x^{n} \), כלומר יש \( 2^{n} \) סדרות בינאריות מאורך \( n \). כמובן, זה דבר שקל לדעת גם בשיטות קומבינטוריות אחרות, אבל קיבלנו את זה כאן בדרך חדשה ושונה לגמרי - בעצם, דרך שהיא חפה כמעט לחלוטין מטיעונים קומבינטוריים (טיעונים שמוחבאים אי שם בהוכחה של ההתאמה בין פעולות אלגבריות על פונקציות יוצרות ופעולות קומבינטוריות על המחלקות המתאימות).

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

תחת ההגדרה הזו צץ תיאור פשוט מאוד של עצים באופן רקורסיבי - “עץ” הוא זוג שכולל צומת יחיד וסדרה של אפס או יותר עצים (הצומת הוא האיבר הראשון בזוג והסדרה היא האיבר השני). אם נסמן ב-\( G \) את מחלקת העצים וב-\( A \) קבוצה שיש בה איבר בודד מגודל 1 (\( A=\left\{ \bullet\right\} \) - חשבו על \( \bullet \) בתור צומת), אז קיבלנו את המשוואה הבאה שמגדירה את \( G \):

\( G=A\times G^{*} \)

המשוואה הזו היא בסך הכל תיאור פורמלי של התיאור המילולי שנתתי למעלה (זוג שכולל את הצומת הבודד של \( A \) ואז סדרה של עצים - \( G^{*} \) היא בדיוק זה). כעת, אם \( g\left(x\right) \) היא הפונקציה היוצרת של \( G \) ו-\( a\left(x\right)=x \) היא הפונקציה היוצרת של \( A \), נקבל מייד ש-\( g=\frac{x}{1-g} \). זה מוביל למשוואה \( g-g^{2}=x \), או בניסוח טיפה שונה \( g^{2}-g+x=0 \), ועל ידי נוסחת השורשים הרגילה נקבל \( g=\frac{1-\sqrt{1-4x}}{2} \).

כמובן שעולות מיד שתי שאלות. ראשית, נוסחת השורשים נותנת שני פתרונות; למה \( \frac{1+\sqrt{1-4x}}{2} \) אינו הפתרון ה”נכון”? ושנית, מה זה בכלל \( \sqrt{1-4x} \) בהקשר ה”פורמלי” שלנו? ובכן, זהו טור חזקות שכאשר כופלים אותו בעצמו מקבלים את \( 1-4x \). האם הוא בהכרח קיים? כאן נחלצת לעזרתנו תוצאה מוכרת - ההכללה של הבינום של ניוטון לחזקות לא שלמות:

\( \left(1+y\right)^{\alpha}=1+\alpha y+\frac{\alpha\left(\alpha-1\right)}{2!}y^{2}+\dots \). האופן שבו מוכיחים את הנוסחה הזו הוא באמצעות אנליזה - מפתחים את הפונקציה \( \left(1+y\right)^{\alpha} \) לטור חזקות. אנחנו עובדים בעולם פורמלי ולא יכולים להשתמש בנימוקים הללו אבל זה לא מונע מהבינום של ניוטון להצביע על האופן שבו \( \sqrt{1+y} \) חייב להיראות, אם יש לו משמעות כטור חזקות: הוא חייב להיות \( 1+\frac{1}{2}y-\frac{1}{8}y^{2}+\frac{1}{16}y^{3}-\frac{5}{128}y^{4}+\dots \) (יש גם צורה כללית סגורה לביטוי: \( \sqrt{1+y}=\sum_{n=0}^{\infty}\frac{\left(-1\right)^{n}\left(2n\right)!}{\left(1-2n\right)\left(n!\right)^{2}4^{n}}y^{n} \) - לא הכי יפה, חייבים להודות). אם טורחים לשבת ולכפול את טור החזקות הזה בעצמו, פורמלית, מקבלים את \( 1+y \), כך שגם מבחינה פורמלית לחלוטין אין לנו בעיות עם שורשים פשוטים.

כעת, אם מציבים במקום \( y \) את \( -4x \) מקבלים \( 1-2x-2x^{2}-4x^{3}-10x^{4}+\dots \). אם לזה היינו מוסיפים 1 ומחלקים ב-2, היינו מקבלים תוצאה לא קומבינטורית בעליל - טור חזקות שיש לו מקדמים שליליים, כך שהפתרון \( \frac{1+\sqrt{1-4x}}{2} \) אינו יכול להיות הפתרון המתאים לבעיה שלנו; הפתרון חייב להיות \( \frac{1-\sqrt{1-4x}}{2} \), שנותן לנו את הסדרה \( x+x^{2}+2x^{3}+5x^{4}+\dots \). אם נאזור אומץ ונציב \( y=-4x \) בנוסחה הכללית שתיארתי למעלה ונבצע את כל הפישוטים, נקבל שהפונקציה היוצרת היא \( \sum_{n=1}^{\infty}\frac{\left(2n\right)!}{2\left(2n-1\right)\left(n!\right)^{2}}x^{n} \). אפילו את זה אפשר לפשט עוד טיפה אם שמים לב לכך ש-

\( \frac{\left(2n\right)!}{2\left(2n-1\right)\left(n!\right)^{2}}=\frac{\left(2n\right)\cdot\left(2n-1\right)\cdot\left(2n-2\right)!}{2\left(2n-1\right)n^{2}\left(\left(n-1\right)!\right)^{2}}=\frac{1}{n}{2n-2 \choose n-1} \)

כלומר, בסופו של דבר \( g\left(x\right)=\sum_{n=1}^{\infty}\frac{1}{n}{2n-2 \choose n-1}x^{n} \). שימו לב לטכניקות הלא קומבינטוריות בעליל שהשתמשנו בהן כאן; הקומבינטוריקה נגמרה באבחנה הפשוטה (והיפה) לפיה \( G=A\times G^{*} \); מכאן זה היה תהליך אלגברי/אנליטי סטנדרטי לגמרי - קצת מלוכלך כשעושים אותו ביד בפעם הראשונה, אבל לא משהו רציני למי שכבר משופשף בעניינים הללו ובוודאי שלא בעיה למערכת אלגברה ממוחשבת שתפקידה להתמודד עם משוואות כאלו. בסופו של דבר הגענו אפילו לנוסחה סגורה: מספר העצים הוא \( \frac{1}{n}{2n-2 \choose n-1} \). עכשיו כבר אפשר לגלות את הסוד: המספרים \( C_{n}=\frac{1}{n+1}{2n \choose n} \) מוכרים מאוד בקומבינטוריקה ונקראים “מספרי קטלן”; מה שהוכחנו פה הוא שמספר העצים על \( n \) קודקודים הוא בדיוק מספר קטלן ה-\( n-1 \) (למי שמכיר את מספרי קטלן אולי נופל פתאום אסימון; מספרי קטלן ניתנים להגדרה באמצעות נוסחת נסיגה שגם היא משתמשת בקונבולוציה).

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