מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/צירופים

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

< מתמטיקה תיכונית | אלגברה תיכונית | קומבינטוריקה(הופנה מהדף אלגברה תיכונית/קומבינטוריקה/צירופים)

תוכן עניינים

1 צירופים
2 דוגמה לחלוקת קלפים במשחק ברידג'
- 2.1 בעיה
- 2.2 פתרון

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

בהגרלת לוטו עולים בגורל שבעה מספרים מתוך שלושים. כמה תוצאות אפשריות יש להגרלה?

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

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

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

הגדרה:

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

נוכיח בהמשך כי מספר האפשרויות לבחור $\ k$ איברים מתוך $\ n$ (כאשר $\ k\le n$ ) הוא $\ \frac{n!}{k!(n-k)!}$ . גודל זה הוא בעל חשיבות גדולה במתמטיקה והוא מופיע במקומות רבים ושונים, ועל כן נותנים לו סימון מיוחד: $\ {n\choose k}=\frac{n!}{k!(n-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}$ , ובכך הושלמה ההוכחה.

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

[עריכה] בעיה

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

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

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

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