מהי קומבינטוריקה?

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

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

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

קרוב לודאי שרבים מכם שואלים את עצמכם על הקומבינטוריקה בפרט את אותה שאלה שלעתים שואלים על המתמטיקה בכלל - למי אכפת? למי אכפת אם יש 113,332,442 צירופים אפשריים לפרוזן יוגורט בדוכן הקרוב, ולא סתם 113,332,441? מה המספר הזה נותן לנו בכלל? מה הטעם בכל זה?

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

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

עם זאת, לפעמים אנחנו מתעניינים מאוד במספרים המדוייקים, עד לספרה האחרונה. סיבה מרכזית אחת לכך היא שמספרים מדוייקים מאפשרים לנו למצוא קשרים בין בעיות שנראות שונות מהותית. הנה דוגמה קלאסית: סדרה חוקית של סוגריים היא סדרת של סמלים שהם או \( ")" \) (סוגר ימני) או \( "(" \) (סוגר שמאלי), כך שבשום שלב, בקריאה משמאל לימין של הסדרה, לא נוצר מצב שבו קראנו יותר סוגרים ימניים משמאליים (כלומר, לא “סגרנו” סוגריים שבכלל לא נפתחו). כך למשל הסדרה \( ()(()) \) היא חוקית ואילו \( )(() \) אינה חוקית. לא קשה כל כך להראות שהסדרה \( a_{n} \) שבה \( a_{n} \) מייצג את מספר הסדרות החוקיות שמכילות \( n \) סוגריים שמאליים ו-\( n \) סוגריים ימניים מתחילה עם הערכים הבאים: \( 1,2,5,14,42,132,429 \).

נעבור לבעיה לחלוטין לא קשורה - שילוש של מצולע משוכלל. מצולע משוכלל עם \( n \) צלעות הוא מצולע שבו כל הצלעות וכל הזוויות הפנימיות שוות בגודלן. למשל: משולש שווה צלעות. למשל: ריבוע. למשל: משושה משוכלל, וכן הלאה. כשעוסקים במצולעים במדעי המחשב - בעיקר בגרפיקה - נוח לעתים קרובות לפרק אותם למשולשים על ידי מתיחת קווים בין קודקודים קיימים עד שהצורה חולקה כולה למשולשים (לפעולה זו קוראים שילוש - טריאנגולציה). נשאלת השאלה - כמה שילושים שונים קיימים למצולע בעל \( n \) צלעות? מכיוון שעבור \( n=1,2 \) אין בכלל מצולעים בעלי \( n \) צלעות, אני “ארמה” טיפה: \( b_{n} \) יסמן את מספר השילושים של מצולע בעל \( n+2 \) צלעות. והנה זה פלא: הסדרה \( b_{n} \) גם היא מתחילה עם הערכים \( 1,2,5,14,42,132,429 \). זה מייד מדליק אצלנו נורת איתות בראש - הייתכן שיש קשר בין שתי הבעיות, בעיית הזוגות החוקיים של סוגריים ובעיית הטריאנגולציה? וכדי לאמת את החשדות שלנו אנחנו מחשבים (באמצעות מחשב) עוד כמה ערכים של הסדרות - והנה, כל ערך חדש שאנו מחשבים אכן יהיה זהה. וזה מוסיף ומחזק את האמונה שלנו ששתי הסדרות הללו חד הן, עד לשלב שבו נטרח לקחת עט ונייר ולהוכיח את הקשר בין שתי הסדרות. ההוכחה עצמה אינה טריוויאלית אך גם אינה מסובכת מדי, והסדרה \( a_{n} \) היא סדרה כה מעניינת ומרכזית ומופיעה בעוד הקשרים רבים ושונים שהיא זכתה לשם מיוחד: “מספרי קטלן”. למעשה, קיימת אפילו נוסחה סגורה עבורם, אך לא אציג אותה כעת.

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

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

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

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

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

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

מכאן ואילך ההמשך הוא באותה הרוח: יש 50 אפשרויות לבחירת הקלף השלישי, 49 לבחירת הרביעי, וכן הלאה. כשהגענו לקלף האחרון נותרה לנו רק בחירה אחת - שלו בלבד - ולכן יש אפשרות אחת בלבד. בסיכומו של דבר עיקרון הכפל ייתן לנו את התוצאה \( 52\cdot51\cdot50\cdots3\cdot2\cdot1 \). מספר זה ניתן לכתוב גם כ-\( 1\cdot2\cdots52 \) (הרי אין חשיבות לסדר ביצוע פעולות הכפל). מכיוון שדבר שכזה - הכפלה של כל המספרים מ-1 ועד \( n \) - היא דבר נפוץ למדי במתמטיקה (ובקומבינטוריקה בפרט) נהוג לתת לה שם וסימון מיוחד: למכפלה \( 1\cdot2\cdots n \) (כאשר \( n \) הוא תמיד מספר טבעי חיובי) קוראים “\( n \) עצרת”ומסמנים אותה ב-\( n! \) (\( n \) ואז סימן קריאה - כמו רוב הסימונים, אין מאחוריו יותר מדי הגיון מחוכם אלא בעיקר קונבנציה שבחר מישהו והשתרשה במהלך השנים).

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

אבל רגע, אני בעצם משקר, כי בהרבה משחקים אין חשיבות גדולה עד כדי כך לסדר החבילה. בואו ניקח לדוגמה את משחק הברידג’: מחלקים את 52 הקלפים לארבעה שחקנים, 13 קלפים לכל שחקן. אין חשיבות לשאלת הסדר שבו כל שחקן קיבל את הקלפים, אלא רק לשאלה אילו קלפים הוא קיבל. אם כן, הבה ונשאל שאלה אחרת - בכמה דרכים שונות אפשר לבחור 13 קלפים מתוך חבילה של 52 קלפים אם אין חשיבות לסדר שבו הקלפים נבחרים?

עם הבעיה הזו אפשר להתמודד בעזרת הכלי שכבר רכשנו - מספר הפרמוטציות של \( n \) איברים. הבה ונניח ש-13 הקלפים נבחרים באופן הבא: ראשית מערבבים את החבילה, וכעת נותנים לשחקן את 13 הקלפים הראשונים בערבוב. אחרי שנותנים לו אותם הסדר הפנימי של הקלפים “נמחק”, ולכן אם נספור כל ערבוב של החבילה באופן שונה, נבצע ספירה כפולה. מכיוון שזה מבלבל קצת בהתחלה, הבה ונביט בדוגמה פשוטה יותר: נניח שיש לנו חבילה שכוללת ארבעה קלפים בלבד: \( \mbox{A,K,Q,J} \), ושהשחקן רוצה לקבל שניים מהם. כבר את ארבעת הקלפים הללו ניתן לערבב בצורות רבות - 24, ליתר דיוק - ולכן לא אראה את כולן אלא אשאל שאלה אחרת: בכמה דרכים שונות אפשר לערבב את החבילה כך שהשחקן יקבל את \( \mbox{A,K} \)?

ובכן, אלו הן האפשרויות (שתי האותיות שמצד שמאל הן מה שהשחקן יקבל): \( \mbox{AKQJ,AKJQ,KAQJ,KAJQ} \). ספרנו ארבע פעמים חלוקה שהיינו אמורים לספור רק פעם אחת. איך אפשר לנטרל זאת? הצעד הראשון יהיה לשים מעין “מחיצה” שתפריד בין מה שהשחקן מקבל ומה שלא: \( \mbox{AK|QJ,AK|JQ,KA|QJ,KA|JQ} \). כעת נשאל את עצמו - מה קורה מכל אחד מעברי המחיצה? בצד שמאל אנחנו “בוחרים” את אחת משתי הפרמוטציות האפשריות של האיברים \( \mbox{A,K} \), ובצד ימין אנו “בוחרים” את אחת משתי הפרמוטציות האפשריות של האיברים \( \mbox{J,Q} \). בצורה הזו מתקבלות כל האפשרויות לבנות חלוקה של \( \mbox{A,K,Q,J} \) שבה \( \mbox{A,K} \) בצד שמאל ו-\( \mbox{Q,J} \) בצד ימין.

חזרה לבעיה שלנו - כאן יש 13 קלפים בצד שמאל, ו-39 קלפים בצד ימין. לכן יש \( 13! \) אפשרויות לבחור סידור לקלפים בצד שמאל, ו-\( 39! \) אפשרויות לבחור סידור לקלפים בצד ימין, ולכן על פי עקרון הכפל יש \( 13!\cdot39! \) אפשרויות לבחור סידורים לכל הקלפים גם יחד כל עוד תובעים ש-13 הקלפים שבצד שמאל ישארו כולם בצד שמאל. במילים אחרות - לכל בחירה של \( 13 \) קלפים, יש בדיוק \( 13!\cdot39! \) ערבובים של החבילה שבה \( 13 \) הקלפים הללו הם אלו שנבחרים.

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

אם כן, אם אנחנו יודעים את כמות הרגליים בעדר, ואנו יודעים שלכל כבש ארבע רגליים, משמעות הדבר היא שספרנו כל כבש ארבע פעמים, ולכן כדי לקבל את מספרם של הכבשים צריך לחלק את מה שספרנו ב-4. כך גם בדוגמה שלנו: יש \( 52! \) ערבובים שונים של החבילה - זה מספר הרגליים; וכל חלוקת \( 13 \) קלפים נספרה \( 13!39! \) פעמים - זה מספר הרגליים שיש לכבש; ולכן יש בסך הכל \( \frac{52!}{13!39!} \) חלוקות שונות. גם זה מספר עצום - \( 635013559600 \), אבל הוא קטן משמעותית מ-\( 52! \).

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