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

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

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

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

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

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

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

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

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

פתרון. נמיר את הבעייה לבעייה אחרת. נספור את כמות האפשרויות לבחור k חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא $k!$).

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

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

תרגיל. כמה פתרונות שלמים אי שליליים יש למשוואה $x_1+...+x_n=k$?

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

למשל נביט בפתרונות שונים למשוואה $x_1+x_2+x_3=2$:

$0+1+1\leftrightarrow |1|1$

$0+0+2\leftrightarrow ||11$

$1+0+1\leftrightarrow 1||1$

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

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

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

פתרון.

נשים לב שזה תרגיל שקול לתרגיל הקודם. נקרא לאיברים בקבוצה $a_1,...,a_n$. נסמן את מספר הפעמים ש$a_n$ נבחר ב-$x_n$ (שלם אי שלילי). כמובן שסכום $x_n$ חייב להיות k.

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

תרגיל ממבחן 2009 מועד א' (ד"ר אלי בגנו וד"ר שי סרוסי)

א. בכמה דרכים ניתן לבחור שני מספרים שונים מ1 עד 100 שסכומם זוגי? הוכח.

1. ${50 \choose 2}+{50 \choose 2}$

2. ${50 \choose 2}\cdot {50 \choose 2}+{50 \choose 2}$

3. ${50 \choose 2}\cdot 50!$

4. ${50+2-1 \choose 50-1}$

ב. בכמה דרכים ניתן לבחור 3 מספרים שונים מ1 עד 100 שסכומם זוגי? הוכח.

1. ${50 \choose 1}\cdot {50 \choose 2}+{50 \choose 3}$

2. ${50 \choose 2}\cdot {50 \choose 2}+{50 \choose 2}$

3. ${50 \choose 2+1}\cdot 3!$

4. ${50+3-1 \choose 50-1}$

ג. נתונה קבוצה סופית A. נסמן ב-C את קבוצת היחסים על A. מהו מספר הפונקציה החח"ע מC אל A? הוכח.

פתרון.

א. ניתן לבחור כל מספר מ1 עד 100. כעת, המספר המתאים לו צריך להיות מאותה זוגיות על מנת שהסכום יהיה זוגי. לכן בבחירה הראשונה היו לנו 100 אפשרויות ובשנייה 49. כעת, סדר הזוג לא משנה לכן נחלק ב2. סה"כ התוצאה היא $50\cdot 49$. זה בדיוק שווה לסעיף 1, שכן ${50 \choose 2}+{50 \choose 2}+2{50 \choose 2} = 2\frac{50!}{2!48!}=2\frac{50\cdot 49}{2}$

דרך אחרת להסתכל על הפתרון: נבחר 2 זוגיים, או 2 אי-זוגיים.

ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. ${50 \choose 3}+{50\choose 2}\cdot{50 \choose 1}$

ג. נסמן $|A|=a$. מספרים היחסים על A הוא קבוצת החזקה של $A\times A$ שזה $2^{|A\times A|}=2^{a^2}$. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה $n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{k!}$ איברים.

אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו $2^{a^2}>a$ ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.

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

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