הבינום של ניוטון

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

בשלב כלשהו בתיכון נלמדת הנוסחה הפשוטה הבאה: \( \left(a+b\right)^{2}=a^{2}+2ab+b^{2} \). למה? ככה. לפעמים גם נלמדת נוסחה יותר מסובכת: \( \left(a+b\right)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3} \). כשהייתי בתיכון תיעבתי את הנוסחה הזו, עם החזקה השלישית - אף פעם לא זכרתי בדיוק איך היא הולכת ונאלצתי לבדוק בדף הנוסחאות. כעת, כשאני כותב את הפוסט, לא נזקקתי כלל לדף נוסחאות כלשהו - וזה לא שהזכרון שלי השתפר במיוחד או שאני משתמש בנוסחה הזו על בסיס יומיומי. אני מקווה שעד סיום הפוסט גם כל הקוראים יוכלו לכתוב את הנוסחה הזו “מהראש” וללא צורך בשום דף נוסחאות או אפילו חישובים ידניים.

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

במתמטיקה באופן כללי הדרך הטובה להבין מקרה כללי היא לעתים קרובות דרך בחינת מקרים פרטיים פשוטים, אפילו פשוטים ברמה מגוחכת. \( \left(a+b\right)^{1} \) הוא פשוט \( a+b \), וזה לא מלמד אותנו הרבה; אבל \( \left(a+b\right)^{2} \) זה כבר סיפור שונה. איך באמת מגיעים לאותה נוסחה מפורסמת של \( a^{2}+2ab+b^{2} \)?

לצורך כך בואו ונחזור רגע ליסודות. תשכחו מהבינום - איך מבצעים את פעולת הכפל הבאה - \( \left(a+b\right)\cdot c \)? כאן בא לעזרתנו אחד מחוקי החשבון הבסיסיים ביותר - חוק הפילוג, שקובע פשוט ש-\( \left(a+b\right)c=ac+bc \).

השלב הבא הוא המכפלה \( \left(a+b\right)\left(c+d\right) \). גם כאן אפשר להשתמש בחוק הפילוג בדיוק באותו האופן כמו קודם, ולקבל \( \left(a+b\right)\left(c+d\right)=a\left(c+d\right)+b\left(c+d\right) \). כעת אפשר להשתמש בחוק הפילוג שוב (הפעם בגרסה שלו שאומרת ש-\( c\left(a+b\right)=ca+cb \)) ולקבל \( a\left(c+d\right)+b\left(c+d\right)=ac+ad+bc+bd \). עד כאן חשבון פשוט - מה הקשר לקומבינטוריקה?

ובכן, אני רוצה שנחשוב על המכפלה \( \left(a+b\right)\left(c+d\right) \) באופן שונה - בתור תהליך של בחירה. בפתיחת הסוגריים, כל מחובר שנקבל בסכום הסופי מתקבל מבחירה של איבר אחד בסוגר השמאלי, בחירה של איבר אחד בסוגר הימני, והכפלתם. כך \( ac \) מתקבל כשנבחר האיבר הראשון בכל זוג סוגריים, \( bd \) מתקבל כשנבחר האיבר השני, וכן הלאה. שימו לב לסדר שבו כתבתי את האיברים: כתבתי \( ac \) ולא \( ca \) (למרות ששני ערכים אלו שווים אלו לאלו) כדי להבליט את העובדה ש-\( a \) נבחר מהסוגריים השמאליים ואילו \( c \) מהסוגריים הימניים.

עכשיו בואו נעבור לטפל ב-\( \left(a+b\right)^{2} \), שהוא מקרה פשוט יותר מהמקרה הכללי: \( \left(a+b\right)^{2}=\left(a+b\right)\left(a+b\right) \) ואחרי פתיחת הסוגריים נקבל את הסכום \( aa+ab+ba+bb \). כעת אפשר לשפר את מראה הסכום הזה: את \( aa \) אפשר להחליף ב-\( a^{2} \), ובמקום להסתבך עם \( ab \) ו-\( ba \) אפשר להשתמש בחוק החילוף ולקבל \( ab+ba=ab+ab=2ab \). הנה כי כן הגענו ל-\( a^{2}+2ab+b^{2} \), אבל לדעתי יותר חשוב לזכור דווקא את התוצאה ה”גולמית”: \( aa+ab+ba+bb \).

בואו נעבור לטפל במקרה קשה הרבה יותר: \( \left(a+b\right)^{3}=\left(a+b\right)\left(a+b\right)\left(a+b\right) \). כאן אפשר לחשוב על תהליך פתיחת הסוגריים כעל תהליך של בחירת שלושה איברים והכפלתם - איבר אחד מכל סוגר. התוצאה הסופית תהיה סכום שבו כל מחובר מתקבל מבחירת איבר מכל אחד מזוגות הסוגריים. אם נכתוב במפורש את כל התוצאות (קצת טרחני, אני יודע) נקבל: \( aaa+aab+aba+abb+baa+bab+bba+bbb \). האם תוכלו להגיד לי, בלי לספור, כמה מחוברים יש? זו כבר שאלה קומבינטורית לגמרי: יש שלושה זוגות סוגריים, ומכל זוג אנו בוחרים אחד משני איברים - על כן, לפי עיקרון הכפל, יש לנו \( 2\cdot2\cdot2=8 \) אפשרויות בחירה (כי הבחירה שלנו מורכבת משלושה שלבים שבכל אחד מהם יש שתי אפשרויות בחירה) ולכן יש שמונה מחוברים בסכום - עכשיו אפשר לבדוק זאת ידנית.

כעת, כיצד ניתן לפשט את הזוועה של שמונת המחוברים? את \( aaa \) אפשר להחליף ב-\( a^{3} \). את \( aab \) אפשר להחליף ב-\( a^{2}b \). גם את \( aba \) אפשר להחליף ב-\( a^{2}b \) וגם את \( baa \) אפשר להחליף ב-\( a^{2}b \). אם כן, כמה פעמים יופיע \( a^{2}b \) בסכום הסופי? כמספר הפעמים שבהן אפשר לבחור מבין שלושת הסוגריים פעמיים את \( a \), ופעם אחת את \( b \). אלו בדיוק שלוש פעמים - אפשר לחשוב על כך בשתי דרכים שונות: או שאנו בוחרים את שני זוגות הסוגריים שמהם ניקח \( a \) ואז ממה שנשאר לוקחים \( b \), או שבוחרים את הסוגר שממנו ניקח את \( b \) ואומרים שמשני הנותרים ניקח \( a \). בדרך השנייה ברור לגמרי שיש רק שלוש אפשרויות (יש שלושה זוגות סוגריים). בדרך הראשונה זה קצת פחות ברור ולכן הגיע הזמן לקרוא לעזרת הכלי שלמדנו בפעם הקודמת: מספר האפשרויות לבחור \( k \) איברים מתוך \( n \) הוא \( \frac{n!}{k!\left(n-k\right)!} \) - ביטוי שלצורך פשטות סימנו בסימון \( {n \choose k} \), ואצלנו \( n=3 \) ו-\( k=2 \) כך שנקבל \( \frac{3!}{2!1!}=\frac{6}{2}=3 \).

בואו נחזור לרגע אל \( a^{3} \) ידידנו - כמה פעמים הוא יופיע בסכום? כמספר הפעמים שבהן ניתן לבחור \( a \) בכל שלושת זוגות הסוגריים - אבל יש בדיוק רק בחירה אחת שכזו. פורמלית זה שווה למספר האפשרויות לבחור שלושה איברים מתוך שלושה: \( {3 \choose 3}=1 \).

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

אוקיי, עכשיו אתם ככל הנראה שואלים את עצמכם מה לעזאזל עשיתי כאן. במקום לקבל, כמו שהבטחתי, משהו פשוט ויפה קיבלתי ביטוי שנראה כמו זוועת עולם. אלא שאני טוען שהביטוי כלל אינו מזוויע, אחרי שעובר ההלם הראשוני, ויש בו יתרון גדול - קל לזכור אותו. שימו לב לכך שהוא מאוד תבניתי: סכום של איברים מהצורה \( {3 \choose i}a^{i}b^{3-i} \) כשהדבר היחיד שמשתנה הוא ערכו של ה-\( i \). זה דבר שקל לזכור. לא באמת צריך לזכור מה ערכו המדוייק של כל מקדם, אלא רק שכל מקדם הוא מהצורה \( {3 \choose i} \) עבור ה-\( i \) המתאים. כשכתבתי את הנוסחה שבתחילת הפוסט “מהראש”, זה מה שהשתמשתי בו.

כעת אני רוצה לקפוץ קצת קדימה ולהציג סימון שבתיכון לא נהוג להשתמש בו (וחבל). כבר אמרתי שהנוסחה שלי ל-\( \left(a+b\right)^{3} \) היא סכום של איברים שכולם נראים כמעט אותו דבר: \( {3 \choose i}a^{i}b^{3-i} \), כשהדבר היחיד שמשתנה הוא ה-\( i \). הדרך המתמטית לכתוב זאת היא באמצעות האות היוונית \( \Sigma \) (סיגמה גדולה) שבאה לציין את המילה “סכום” (בשפה המתאימה, כמובן…). הנה הסימון: \( \left(a+b\right)^{3}=\sum_{i=0}^{3}{3 \choose i}a^{i}b^{3-i} \).

מה יש לנו פה? ובכן, אחרי הסיגמה יש לנו את \( {3 \choose i}a^{i}b^{3-i} \) שכבר הזכרתי מספיק - זהו האיבר הכללי של הסכום. איבר כללי במובן זה שכל מחובר בסכום נראה כמוהו, לאחר הצבה של ערך מתאים ב-\( i \). האות \( i \) נקראת האינדקס של הסכימה, והמספרים שכתובים מתחת ומעל לסיגמה באים לציין את הערכים שאותם \( i \) מקבל; \( i=0 \) אומר שהערך הראשון ש-\( i \) מקבל הוא 0, וה-3 למעלה אומר שזהו הערך האחרון שהוא מקבל. המוסכמה היא שאלא אם נאמר במפורש אחרת, \( i \) מקבל רק ערכים שלמים, ולכן הסכום מתאר את מה שמקבלים כאשר מציבים באיבר הכללי את הערכים \( i=0,1,2,3 \).

אני מקווה שסימן הסכימה ברור כעת ולא מפחיד; שאלה אחת שאולי התעוררה בכם היא למה לא לכתוב \( \sum_{0}^{3}{3 \choose i}a^{i}b^{3-i} \) וחסל - למה צריך את ה-\( i= \) למטה? התשובה היא שלא תמיד ברור מהו האינדקס - לפעמים (ונראה דוגמה ממש בקרוב) יש יותר ממשתנה אחד שמופיע באיבר הכללי, וצריך להבהיר מי משמש כאינדקס הסכימה. עם זאת אעיר שכשההקשר ברור, לעתים קרובות נהוג להשמיט פרטים מסימן הסכימה, עד כדי כך שלפעמים אפשר למצוא נוסחאות כמו \( \sum a_{i} \) וחסל - כאן השאלה אילו ערכים האינדקס מקבל תלויה לחלוטין בהקשר, וכותבי הטקסט מצפים שהקורא יוכל להסיק את המידע הזה בעצמו. באופן לא מפתיע, בטקסטי מבוא לרוב אין זוועות שכאלה.

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

ובכן, למה הנוסחה נכונה? בדיוק אותם שיקולים כמו קודם. \( \left(a+b\right)^{n} \) ניתן לכתיבה כמכפלה של \( n \) זוגות סוגריים, ולכן התוצאה הסופית תהיה סכום של איברים שהתקבלו מבחירת \( a \)-ים ו-\( b \)-ים - סה”כ \( n \) פעמים עבור שניהם. אם \( i \) הוא מספר ה-\( a \)-ים שנבחרו, אז נקבל איבר מהצורה \( a^{i}b^{n-i} \), ויש לנו בדיוק \( {n \choose i} \) דרכים שונות לבחור \( i \) \( a \)-ים, וזהו. מה שכתבתי כאן הוא כמעט הוכחה מתמטית, והוא בוודאי מבהיר היטב למה הנוסחה נראית כמו שהיא נראית ואיך זה קשור לקומבינטוריקה (ואם זה עדיין לא ברור - זו אשמתי, לא אשמת ההוכחה). לטעמי הוכחה זו (הגם שאינה פורמלית במאה אחוזים) טובה בהרבה מההוכחה ה”יבשה” לנכונות הבינום, שמשתמשת באינדוקציה מתמטית מזוויעה.

אם כן, זהו זה. נפתרה הבעיה הכללית של \( \left(a+b\right)^{2} \) ו-\( \left(a+b\right)^{3} \) וכל חזקה טבעית אחרת, והנוסחה הסופית היא קצרה ויפה להצגה (אבל חשבו כמה מזוויע יהיה לכתוב באופן מפורש את \( \left(a+b\right)^{13} \)!). כעת אני מקווה כי גם ברור מדוע \( {n \choose i} \) נקראים “מקדמי הבינום” - מכיוון שהם המקדמים של הגורמים מהצורה \( a^{i}b^{n-i} \) בפיתוח נוסחת הבינום. אני גם מקווה שכעת ברור קצת יותר איך הקומבינטוריקה מתקשרת לתחומים אחרים במתמטיקה (כאן - אלגברה בסיסית) ומסייעת לנו להבין גם אותם.