88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 9

מבוא לקומבינטוריקה

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

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

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

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

דוגמא. בכמה דרכים אפשר לסדר n אנשים בתור?

פתרון. כל אחד יכול להיות ראשון בתור לכן כבר יש n אפשרויות. כעת, נניח ואיציק ראשון בתור, נותר לסדר n-1 אנשים אחריו בתור. נניח באינדוקציה שמספר האפשרויות לסדר n-1 אנשים בתור הוא [math]\displaystyle{ (n-1)! }[/math] ונקבל שמספר האפשרויות שלנו הוא [math]\displaystyle{ n\cdot (n-1)! = n! }[/math].

דוגמא. בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).

פתרון. נמיר את הבעייה לבעייה אחרת. נספור את כמות האפשרויות לבחור k חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא [math]\displaystyle{ k! }[/math]).

אם כך, אנו מעוניינים לדעת כמה אפשרויות יש לנו לבחור k חפצים מתוך n חפצים כאשר הסדר שלהם משנה. נסדר את n החפצים בשורה וניקח את k הראשונים. כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותרים.

אם כך, קיבלנו נוסחא [math]\displaystyle{ {n \choose k} = \frac{n!}{k!(n-k)!} }[/math]

תרגיל. כמה פתרונות שלמים אי שליליים יש למשוואה [math]\displaystyle{ x_1+...+x_n=k }[/math]?

פתרון. נחלק את המספר k לאחדות, ונשים בין האחדות n-1 חוצצים שונים. המשתנה ה-s הוא מספר האחדות שבין החוצץ ה-s לקודמו.

למשל נביט בפתרונות שונים למשוואה [math]\displaystyle{ x_1+x_2+x_3=2 }[/math]:

[math]\displaystyle{ 0+1+1\leftrightarrow |1|1 }[/math]

[math]\displaystyle{ 0+0+2\leftrightarrow ||11 }[/math]

[math]\displaystyle{ 1+0+1\leftrightarrow 1||1 }[/math]

אם כן, נספור את מספר האפשרויות לסדר את החוצצים. נשים בשורה את כל האחדות ואת כל החוצצים, סה"כ נקבל [math]\displaystyle{ n+k-1 }[/math] איברים. מספר האפשרויות לסדר אותם הוא [math]\displaystyle{ (n+k-1)! }[/math]. כעת, צריך לחלק בחזרות המיותרות: סדר החוצצים אינו משנה, וכמו כן סדר האחדות אינו משנה. לכן סה"כ מספר האפשרויות הינו [math]\displaystyle{ {n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!} }[/math]

תרגיל. כמה דרכים יש לבחור k איברים מתוך קבוצה של n איברים כאשר מותר לי לבצע חזרות ולא משנה לי סדר האיברים?

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

פתרון.

נשים לב שזה תרגיל שקול לתרגיל הקודם. נקרא לאיברים בקבוצה [math]\displaystyle{ a_1,...,a_n }[/math]. נסמן את מספר הפעמים ש[math]\displaystyle{ a_n }[/math] נבחר ב-[math]\displaystyle{ x_n }[/math] (שלם אי שלילי). כמובן שסכום [math]\displaystyle{ x_n }[/math] חייב להיות k.

בדוגמא לעיל נסמן [math]\displaystyle{ \{0,1\}=\{a_1,a_2\} }[/math]. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה [math]\displaystyle{ x_1+x_2=2+1=3 }[/math], וכדומה.

טבלת סיכום לנוסחאות בסיסיות ידועות

בעייה	מספר האפשרויות
מספר האפשרויות לסדר n אנשים שונים בשורה	[math]\displaystyle{ n! }[/math]
מספר האפשרויות לבחור קבוצה של k תלמידים מתוך כיתה של n תלמידים	[math]\displaystyle{ {n \choose k} = \frac{n!}{k!(n-k)!} }[/math]
מספר האפשרויות לבנות סדרה עם k איברים מתוך קבוצה המכילה מ איברים	[math]\displaystyle{ n^k }[/math]
מספר האפשרויות לבנות סדרה עם k איברים שונים מתוך קבוצה המכילה n איברים	[math]\displaystyle{ \frac{n!}{(n-k)!} }[/math]
מספר האפשרויות לבחור k איברים מתוך n איברים כאשר אין משמעות לסדר הבחירה ומותר לחזור על הבחירה	[math]\displaystyle{ {n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!} }[/math]