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

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

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

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

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

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

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

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

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

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

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

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

שני העקרונות הבסיסיים בקומבינטוריקה נקראים "עקרון החיבור" ו"עקרון הכפל" ובמבט ראשונים הם עשויים להיראות פשוטים עד כדי גיחוך, אפילו מיותרים. עקרון החיבור אומר כי אם יש לנו שתי דרכי פעולה אפשריות, בדרך הפעולה הראשונה יש לנו $latex a$ בחירות, ובדרך הפעולה השנייה יש לנו $latex b$ בחירות, והבחירות שלנו בדרך הפעולה הראשונה שונות מאלו של דרך הפעולה השנייה – אז בסך הכל יש לנו $latex a+b$ בחירות אפשריות. למשל, אם אנחנו יכולים לקנות אחד מחמישה סוגי גלידה שונים, או אחד מארבעה סוגי פיצות שונים, בסך הכל יש לנו תשע אפשרויות שונות לבחירת זלילה. הדגש כאן הוא על כך שאפשר או גלידה או פיצה, אך לא גם וגם.

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

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

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

אם כן, יש $latex 52!$ ערבובים של חבילות קלפים, ובאופן כללי יש $latex n!$ לסדר בשורה $latex n$ איברים שכולם שונים זה מזה – לסידור שכזה קוראים "תמורה", ובעברית – פרמוטציה. למי שסקרן, הערך המספרי המדוייק של $latex 52!$ הוא $latex 80658175170943878571660636856403766975289505440883277824000000000000$. המספר העצום בגודלו הזה הוא הסיבה לעושר הרב שאפשר למצוא במשחקי קלפים – אין כמעט שום סיכוי שיתקבלו שני ערבובים זהים, ולכן שני משחקים זהים.

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

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

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

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

מה עכשיו? נמחיש עם עוד דוגמה פשוטה קצת יותר. בדיחה ידועה מספרת על ברנש שבא לרועה צאן ולעג לו על שהוא סופר כבשים בצורה כל כך מסורבלת. רעה הצאן הזועם תבע ממנו כאתגר לספור בעצמו כמה כבשים יש בעדר. הברנש השיב מייד וללא היסוס "$latex 139$". רועה הצאן הנדהם שאל אותו "איך ידעת?" ולזה השיב הברנש "ספרתי את הרגליים וחילקתי ב-4".

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

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

27 תגובות על הפוסט “מהי קומבינטוריקה?

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

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

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

  4. בתור מדמ"חניק ההערה האחרונה שלך לא מקובלת עלי. כל אחד צריך להיות מסוגל, לפחות בתיאוריה, ליישם את אלגוריתמי הספירה שלו :-)

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

  6. פינגבאק: משולש פסקל « לא מדויק

  7. נטפוק: בסדרה חורית של סוגריים צריך גם שמספר הסוגריים הימניים יהיה שווה למספר הסוגריים השמאליים.

  8. שוב אני – מהתגובה למעלה.
    טעות שלי – בויקיפדיה ההדגמה היא עם משושה.

  9. פינגבאק: הבינום של ניוטון « לא מדויק

  10. פינגבאק: כל כך קשה לבחור… « לא מדויק

  11. פינגבאק: למה יש מיון מהיר יותר ממיון מהיר אבל בעצם אין | לא מדויק

  12. פוסט נהדר, רק הערה קטנה: כתבת "לסידור שכזה קוראים "תמורה", ובעברית – פרמוטציה."

  13. פינגבאק: מתפזרים | צדפים על שפת הים

  14. למישהו יש אתר שמסופר בו על ההסטוריה של הקומבינטוריקה? מתי איך ולמה היא התפתחה?
    תודה מראש!

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

  16. גדי, יכול להתפרש מדבריך על משחק הברידג' שיש בו 52! חלקי 13!39! אפשרויות. למעשה, זה לא מדויק – יש 52! חלקי 13!*13!*13!*13! אפשרויות. זה מגביה את המספר שרשמת משמעותית

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

כתיבת תגובה

האימייל לא יוצג באתר.