פונקציות יוצרות

אחת מהבעיות הבסיסיות בקומבינטוריקה היא בעיית הספירה של אובייקטים. יש קבוצה של אובייקטים מסוג מסויים - נניח, מספרים שמקיימים תכונה מסויימת, גרפים שנראים כך וכך, דרכים לחלק גלידה לילדים, קלטים האפשריים לאלגוריתם וכו’, ואנחנו רוצים לדעת כמה בדיוק יש. לרוב התשובה הפשוטה לשאלות הללו היא “אינסוף” (כמה מספרים ראשוניים יש? אינסוף. לא הכי אינפורמטיבי) וצריך לחדד את השאלה - למשל, לשאול “כמה אובייקטים מכל גודל יש”, כש”גודל” מוגדר בהתאם לשאלה. את שאלת המספרים הראשוניים אפשר לחדד ל”כמה מספרים ראשוניים בני \( n \) ספרות יש” (אם כי בפועל, השאלה שבה מתעניינים היא בעיקר “כמה מספרים ראשוניים הקטנים מ-\( n \) קיימים”, וזה ראוי לפוסט נפרד). ב”דרכים לחלק גלידה לילדים” אפשר לדבר על הדרכים לחלק גלידה ל-\( n \) ילדים. כשמדברים על גרפים בעלי תכונה מסויימת, אפשר לדבר על גרפים בעלי \( n \) צמתים שמקיימים את התכונה, וכדומה. בשורה התחתונה, לכל אוסף אובייקטים שכזה אנחנו מתאימים סדרה אינסופית \( a_{0},a_{1},a_{2},\dots,a_{n},\dots \) של מספרים טבעיים, שמתארת כמה אובייקטים מכל “גודל” קיימים.

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

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

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

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

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

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

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

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

עד כה התעסקנו רק במספרים ממשיים, אבל זה לא הכרחי - כל התורה של טורים מתכנסים עוברת היטב גם למספרים מרוכבים, עם אותן תוצאות - לטור מהצורה \( \sum_{n=0}^{\infty}a_{n}x^{n} \) (עכשיו כבר אפשר לומר שיש לו שם מיוחד - “טור חזקות”, Power series) יהיה רדיוס התכנסות \( R \) כך שלכל מספר מרוכב המקיים \( \left|z\right|<R \), הטור יתכנס. מכיוון שאפשר לחשוב על המספרים המרוכבים כעל נקודות במישור דו ממדי, שציר ה-\( x \) שלו הוא המספרים הממשיים, יש משמעות ברורה כעת למונח “רדיוס התכנסות” - לטור חזקות בעל רדיוס התכנסות \( R \) יש עיגול ברדיוס \( R \) שמרכזו בראשית הצירים ובכל נקודה בו (למעט נקודות על השפה) הטור מתכנס. ההרחבה הזו למרוכבים היא מאירת עיניים למדי. לדוגמה, נתבונן בטור \( 1-x^{2}+x^{4}-x^{6}+\dots \), שמתכנס לפונקציה \( \frac{1}{1+x^{2}} \); הטור לא מתכנס לא עבור \( 1 \) ולא עבור \( -1 \), ועם זאת הפונקציה \( f\left(x\right)=\frac{1}{1+x^{2}} \) בכלל לא רומזת שיהיו בעיות בנקודות אלו (שהרי ערכה בהן הוא \( \frac{1}{2} \)). התובנה מגיעה רק כשחושבים על הפונקציה הזו כפונקציה מרוכבת ושמים לב לכך שבנקודה \( x=i \) היא בכלל לא מוגדרת - והרי \( \left|i\right|=\left|1\right|=\left|-1\right|=1 \). הדוגמה הזו זכורה לי כאחת הדוגמאות הראשונות שנתקלתי בהן כהמחשה לצורה שבה המספרים המרוכבים הם הרחבה טבעית של הממשיים, ולטעמי היא עדיין אחת מהיפות שבהן.

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

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

המשוואה שאציג מתבססת על אבחנה פשוטה: אם \( f\left(x\right) \) היא הפונקציה היוצרת של הסדרה \( a_{n} \), אז \( x\cdot f\left(x\right) \) הוא הפונקציה היוצרת של הסדרה \( b_{n} \) שמוגדרת על ידי \( b_{0}=0 \) ו-\( b_{n}=a_{n-1} \) לכל \( n>0 \) (למה?). כלומר, אם \( a_{n} \) הוא “מספר האיברים מגודל \( n \)”, אז \( b_{n} \) יהיה דווקא “מספר האיברים מגודל \( n-1 \)”. כעת לפאנץ’: מהו מספר מסלולי מוצקין מאורך \( n \)? אפשר לחלק את בעיית הספירה הזו לשתי אפשרויות, על פי הצעד הראשון במסלול. אם הצעד הראשון היה פשוט ימינה, אז מספר הדרכים להמשיך את המסלול ולקבל מסלול חוקי הוא כמספר מסלולי מוצקין מאורך \( n-1 \) (שוב, מדוע?). הפונקציה שמתארת את הסדרה הזו היא בדיוק \( xf\left(x\right) \) שלעיל.

אם הצעד הראשון היה למעלה, הרי שמתישהו בהמשך הדרך חייב להיות צעד למטה שיחזיר אותנו לגובה 0. מה קורה בין שני הצעדים הללו? יש תת מסלול, שגם הוא נראה כמו מסלול מוצקין, אם ממקמים את ראשית הצירים שלנו דווקא בנקודה \( \left(1,1\right) \) שאליה הגיע המסלול אחרי העליה. ומה קורה אחרי הירידה? שוב, יהיה לנו מסלול מוצקין חדש, מנקודת הירידה ועד לנקודת הסיום. כלומר, מה היה לנו? שני צעדים “מבוזבזים”, ושני מסלולי מוצקין, כך שכל זוג של שני מסלולים אפשריים ייתן לנו את המסלול המשולב. הפונקציה שמתארת את זה היא \( x^{2}f^{2}\left(x\right) \) (\( x^{2} \) כדי “להפחית” את שני הצעדים שבוצעו; \( f^{2}\left(x\right) \) כי כל מסלול בנפרד הוא \( f\left(x\right) \), ולכן השילוב של שניהם בזה אחר זה נותן \( f\left(x\right)\cdot f\left(x\right) \) - כאן אנחנו מבצעים בדיוק את התעלול שלא היה ניתן לבצע אם היינו מסתכלים על כל \( a_{n} \) לבדו ולא על “כולם ביחד” כמו שמאפשרת לנו \( f\left(x\right) \)). מחיבור שתי האפשרויות (או צעד ימינה, או צעד באלכסון) מקבלים את המשוואה \( f\left(x\right)=xf\left(x\right)+x^{2}f^{2}\left(x\right)+1 \), כאשר ה-\( +1 \) מגיע מכך שאנו סופרים גם את המסלול מאורך 0 (זה “תנאי העצירה” של ההסתכלות הרקורסיבית שלנו על הבעיה). קיבלנו משוואה ריבועית ב”נעלם” \( f\left(x\right) \), שניתן לחלץ ממנה את \( f\left(x\right) \) בטכניקות אלגבריות רגילות - מקבלים \( f\left(x\right)=\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}} \) (למה בחרתי את הפתרון הזה מבין שני פתרונות המשוואה? כי כפי שאראה בהמשך, בסביבות \( x=0 \) הוא מתנהג נחמד ואילו הפתרון השני לא, ולכן לא ייתכן שהפתרון השני מייצג את הטור שלנו).

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

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

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

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

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