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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

הגדרה[עריכה]

טענה 1: בחירה ללא חשיבות לסדר וללא החזרה

מספר האפשרויות לבחור איברים מתוך איברים שונים כאשר הבחירה היא ללא חשיבות לסדר וללא החזרה מסומן ב- או ב- שווה:

נשם לב לדימיון אל הנוסחה עם חשיבות לסדר וללא החזרה:

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

צירופים[עריכה]

הגדרה:

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

הנוסחה למציאת צירופים: (כאשר 0<).

  • מייצג את סך כל האיברים.
  • מייצג את מספר האיברים אותם אנו רוצים לבחור
בשל חשיבותו יש לו סימון יחודי והוא מכונה מקדם בינומי.

נשים לב כי מיידית מהגדרתו נובע כי .


הוכחה:

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

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

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

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

מש"ל.PNG




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

בעיה[עריכה]

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

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

פתרון[עריכה]

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

2. ראשית עלינו לבחור את השחקן שאצלו יהיו כל ארבעת האסים: . כעת עלינו לבחור עוד 9 קלפים עבורו מבין הקלפים שנותרו: . כעת עלינו לבחור קלפים כרגיל עבור שאר השחקנים. באמצעות עקרון הכפל נקבל שהתשובה היא:

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