משולש פסקל

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

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

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

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

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

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

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

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

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

נעבור לדבר על עוד תכונות של משולש פסקל - שעל פי מה שראינו, הן בבסיסן תכונות של מקדמי הבינום. תכונה מעניינת אחת היא שבכל שורה שמספרה הוא ראשוני \( p \), כל אברי השורה (חוץ מה-1-ים שבקצוות) מתחלקים ב-\( p \) (הסיבה לכך - כזכור, \( {p \choose k}=\frac{p!}{k!\left(p-k!\right)} \), מה שאומר בפרט שהמונה הוא כפולה של \( p \), אבל במכנה אין כפולות של \( p \) כי כל המספרים שם קטנים ממנו, ומכיוון ש-\( p \) ראשוני גם מכפלה של איברים במכנה לא תיתן לנו את \( p \)). זו תכונה שבפני עצמה נראית בלתי מזיקה ובלתי מעניינת, אבל היא הופכת לחשובה מאוד כאשר עוסקים במתמטיקה יותר מתקדמת (לסקרנים שלא חוששים מהרבה ג’יבריש: זה מראה שבשדה ממציין \( p \) מתקיים \( \left(x+y\right)^{p}=x^{p}+y^{p} \) ולכן הפונקציה \( \varphi\left(x\right)=x^{p} \) היא הומומורפיזם; למעשה זה אפילו הומומורפיזם עם שם מיוחד - “אנדומורפיזם פרובניוס”, ובאלגברה קומוטטיבית ובתורת גלואה יש לו חשיבות לא מבוטלת).

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

אותו תעלול של הצבה בנוסחת הבינום של ניוטון נותן את התכונה הבאה: לכל שורה, סכום האיברים במקומות הזוגיים פחות סכום האיברים במקומות האי זוגיים הוא אפס (במקרה זה ההצבה היא \( x=1,y=-1 \) - בדקו זאת!).

תעלול חביב במיוחד הוא זה: אם אתם רוצים לראות מהי השורה ה-\( n \)-ית במשולש פסקל, חשבו את \( 11^{n} \). כך למשל תגלו ש-\( 11^{4}=14641 \) - בדיוק איברי השורה הרביעית (\( 1,4,6,4,1 \)). הסיבה לכך פשוטה למדי - כשכופלים מספר ב-11, מחברים אותו עם עצמו כשהוא מוזז בצעד אחד שמאלה. זה אומר שכל ספרה בתוצאה תהיה סכום של שתי הספרות הסמוכות “בשורה שמעליה”. רק מה? צריך להיזהר כאן קצת. \( 11^{5}=161051 \) שלא נראה כלל כמו משולש פסקל, אבל זה נובע מכך שאנחנו משתמשים בבסיס ספירה 10 (כלומר, עם הספרות 0 עד 9 ותו לא), ואילו בשורה החמישית של משולש פסקל כבר יש מספרים גדולים מ-9 שלא ניתן לייצג באמצעות ספרה אחת. אם היינו מציגים את המספרים הגדולים הללו בבסיס אחר - משתמשים, למשל, באות \( A \) כדי לייצג את המספר 10 כספרה בודדת (זה דבר מקובל ולגיטימי לחלוטין - למשל, במחשבים, שפועלים על פי בסיס 16, אכן משתמשים ב-\( A \) למטרה זו, וביתר האותיות הלטיניות עד \( F \). אם אתם רואים כתובת מחשב מוזרה שכוללת בה גם אותיות (כחלק מקריסת המערכת), קרוב לודאי שאתם רואים מספר בבסיס 16), אז היינו מקבלים \( 11^{5}=15AA51 \).

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