מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/צירופים/בחירה ללא חשיבות לסדר וללא החזרה

הגדרה

טענה 1: בחירה ללא חשיבות לסדר וללא החזרה מספר האפשרויות לבחור $k$ איברים מתוך $n$ איברים שונים כאשר הבחירה היא ללא חשיבות לסדר וללא החזרה מסומן ב- $n \choose k$ או ב-$c_{n}^{k}$ שווה: ${n \choose k}={\frac {n!}{k!(n-k)!}}$

נשם לב לדימיון אל הנוסחה עם חשיבות לסדר וללא החזרה: ${\frac {n!}{(n-k)!}}$

מאחר שאין אנו רוצים לספור את האפשרויות החוזרות על עצמן עלינו לחלק ב-$k!$ איברים.

צירופים

הגדרה: צירוף הוא בחירה ללא חשיבות לסדר וללא החזרה.

הנוסחה למציאת צירופים:${\frac {n!}{k!(n-k)!}}$ (כאשר 0<$k$).

• $n$ מייצג את סך כל האיברים.
• $k$ מייצג את מספר האיברים אותם אנו רוצים לבחור

בשל חשיבותו יש לו סימון יחודי ${n \choose k}={\frac {n!}{k!(n-k)!}}={\frac {n(n-1)(n-2)...(n-k+1)(n-k)(n-k-1)*...*3*2*1}{k!(n-k)(n-k-1)(n-k-2)*...*3*2*1}}={\frac {n(n-1)(n-2)...(n-k+1)}{k!}}$ והוא מכונה מקדם בינומי.

נשים לב כי מיידית מהגדרתו נובע כי ${n \choose k}={n \choose n-k}$.

הוכחה:

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

נניח קיימים $n$ איברים מסודרים בשורה. מתוכם אנו רוצים לבחור $k$.

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

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

תרגיל 1: יש חפיסת קלפים סטנדרטית (52 קלפים המחולקים ל4 צורות). מה האפשרות להוציא 6 קלפים מצורת יהלום?
סה"כ מספר הקלפים מצורת יהלום שווה ל-${\frac {52}{4}}=13$ אנו רוצים לקחת 6 קלפי יהלום מתוך 13 אפשרויות (יש להוציא ששה קלפים) ולכן ${13 \choose 6}={\frac {13!}{(13-6)!(6!)}}=1716$

תרגיל 2: יש חפיסת קלפים סטנדרטית (4 צורות עם 13 מספרים). מה האפשרות להוציא 6 קלפים ששנים מהקלפים יהיו עם המספר 6 ועל ארבעה הנותרים מספרים שונים?
${4 \choose 2}{\frac {(52-4)(52-4*2)(52-4*3)(52-4*4)}{4!}}$ אנו רוצים שבשתי אפשרויות נקבל מספר עם הספרה 6 ולכן יש 4 קלפים עם הספרה 6 מתוך שתי מקומות. מאחר שאו רוצים קלפים שונים נותרים לנו 48 קלפים לאפשרות השלישית, 44 לרביעי, 40 לחמישי ו36 לשישי. מכיוון שאין חשיבות לסדר הקלפים יש לנו כפל אפשרויות ולכן עלינו לחלק בעצרת של מספר המחולקים.

דוגמה לחלוקת קלפים במשחק ברידג'

בעיה

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

1. ללא הגבלה.
2. במקרה שבו כל ארבעת האסים נמצאים אצל שחקן אחד.
3. במקרה שבו לאחד הזוגות רק קלפים אדומים ולזוג השני רק קלפים שחורים (מכל סוג ישנם 26 קלפים).

פתרון

1. אנחנו בוחרים 13 קלפים מתוך 52 עבור צפון, 13 קלפים מבין 39 הנותרים עבור מזרח, וכן הלאה. נקבל שמספר האפשרויות הוא: ${52 \choose 13}{39 \choose 13}{26 \choose 13}{13 \choose 13}={\frac {52!}{13!\cdot 39!}}\cdot {\frac {39!}{13!\cdot 26!}}\cdot {\frac {26!}{13!\cdot 13!}}\cdot {\frac {13!}{13!\cdot 1!}}={\frac {52!}{(13!)^{4}}}$.
מכיון שמספר האפשרויות שקיבלנו הוא אדיר לא נכתוב אותו במפורש.

2. ראשית עלינו לבחור את השחקן שאצלו יהיו כל ארבעת האסים: ${4 \choose 1}=4$. כעת עלינו לבחור עוד 9 קלפים עבורו מבין הקלפים שנותרו: ${48 \choose 9}$. כעת עלינו לבחור קלפים כרגיל עבור שאר השחקנים. באמצעות עקרון הכפל נקבל שהתשובה היא: $4\cdot {48 \choose 9}{39 \choose 13}{26 \choose 13}{13 \choose 13}=4\cdot {\frac {48!}{9!\cdot 39!}}\cdot {\frac {39!}{(13!)^{3}}}=4\cdot {\frac {48!}{9!(13!)^{3}}}$

3. ראשית עלינו לבחור לאיזה זוג יהיו הקלפים האדומים: ${2 \choose 1}=2$. כעת עלינו לחלק לו את הקלפים הללו, כלומר לבחור 13 מתוך 26 קלפים לשחקן הראשון, ולתת את הנותרים לשחקן השני. נקבל: ${26 \choose 13}{13 \choose 13}={\frac {26!}{13!13!}}{\frac {13!}{13!1!}}={\frac {26!}{(13!)^{2}}}$. יש לחלק גם את הקלפים השחורים לזוג השני, ובגלל שהבעיה סימטרית מספר האפשרויות זהה. לכן התוצאה הסופית היא $2\cdot \left({\frac {26!}{13!^{2}}}\right)^{2}$.