כל כך קשה לבחור...

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

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

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

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

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

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

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

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

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

הנוסחה לבחירה עם החזרה ועם חשיבות לסדר היא תוצאה ישירה של עקרון הכפל. תהליך הבחירה שלנו הוא בן \( k \) שלבים; בכל שלב אנחנו בוחרים אחת מ-\( n \) אפשרויות שונות. יש לנו אם כן בסך הכל \( n\cdot n\cdots n=n^{k} \) אפשרויות שונות. קל להתבלבל ולשכוח מי במעריך החזקה ומי בבסיס (כלומר, האם זה \( k^{n} \) או \( n^{k} \)) ולכן אני ממליץ לנקוט בגישה הבאה: כמה מספרים דו ספרתיים יש, אם מרשים גם לאפס להופיע (כלומר, \( 3 \) הוא המספר ה”דו ספרתי” \( 03 \) וכדומה)? \( 2^{10} \) או \( 10^{2} \)? ובכן, \( 2^{10}=1024 \) כך שברור שיש כאן בעיה; לעומת זאת \( 10^{2} \) מתאים בדיוק, וזה לא מפתיע כי מספר דו ספרתי מורכב מבחירה של אחת מ-10 הספרות האפשריות בתור ספרת האחדות, ואחת מ-10 הספרות האפשריות בתור ספרת העשרות.

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

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

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

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

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

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

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

לפני שנסיים להפעם אני רוצה לתאר שימוש פשוט אחד בבחירה עם החזרה ובלי חשיבות לסדר, שבינתיים אולי נראית מפחידה ומסובכת ולא מועילה כלל. נביט במשוואה \( x_{1}+x_{2}+\dots+x_{n}=k \), כאשר \( k \) הוא מספר שלם והערכים שאנחנו מרשים למשתנים לקבל הם רק ערכים שלמים אי שליליים (משוואות כאלו צצות בפועל! בעולם האמיתי! תאמינו לי!). כמה פתרונות יש למשוואה הזו? בדיוק מספר האפשרויות לבחור \( k \) איברים מתוך \( n \), עם החזרה ובלי חשיבות לסדר. למה? אשאיר זאת כתרגיל לקורא.