גרסה מ־08:27, 9 באוגוסט 2013

קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון

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

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

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

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

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

מספר האפשרויות לסדר n עצמים שונים בשורה

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

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

מספר האפשריות לבחור k עצמים מתוך n עצמים

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

	אין חזרות	יש חזרות
יש חשיבות לסדר	[math]\displaystyle{ \frac{n!}{(n-k)!} }[/math]	[math]\displaystyle{ n^k }[/math]
אין חשיבות לסדר	[math]\displaystyle{ \;\;\;{n \choose k} = \frac{n!}{k!(n-k)!} \;\;\; }[/math]	[math]\displaystyle{ \;\;\;{n+k-1\choose k}\;\;\; }[/math]

נתחיל לטפל בכל אחד מהמקרים:

יש חשיבות לסדר ויש חזרות

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

דוגמא כמה מספרים בינאריים יש עם 3 ספרות ?

פתרון לספרה הראשונה יש 2 אפשרויות, לספרה השניה יש 2 אפשרויות ולספרה השלישית יש 2 אפשריות ולכן בסה"כ יש [math]\displaystyle{ 2^3 }[/math] וזה כל המספרים. (הבחירה היא הספרות 0,1 כאשר מותר חזרות ויש חשיבות לסדר)

יש חשיבות לסדר ואין חזרות

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

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

פתרון נבחר מתוך הספרות 0-9 שלוש בחירות עם חשיבות לסדר ובלי חזרות ונקבל [math]\displaystyle{ \frac{10!}{(7)!}=10\cdot 9 \cdot 8 }[/math] (לספרה הראשונה יש 10 אפשרויות, לספרה השניה יש רק 9 אפשרויות ולספרה האחרונה נשארו 8 אפשרויות)

אין חשיבות לסדר ואין חזרות

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

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

פתרון. זה שקול לבחור k חפצים כאשר הסדר לא משנה ובלי חזרות ולכן יש [math]\displaystyle{ {n \choose k} }[/math] תתי קבוצות.

מסקנה: [math]\displaystyle{ \sum_{k=0}^n {n \choose k}=2^n }[/math]

הוכחה: ניקח קבוצה X בת n איברים אזי שני האגפים שווים למספר הקבוצות של בקבוצת החזקה.

תרגיל הוכח כי [math]\displaystyle{ {n \choose k}= {n \choose n-k} }[/math]

פתרון לבחור קבוצה של k אברים שקול לבחור n-k אברים שאינם בקבוצה (כלומר לבחור תת קבוצה A זה כמו לבחור את המשלימה שלה)

אתם מוזמנים גם לחשב ישירות.

אין חשיבות לסדר ויש חזרות

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

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

למשל נביט בפתרונות שונים למשוואה [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] מקומות שצריך למלא (k אחדות ו n-1 חוצצים) וצריך לבחור מתוכם את המקומות של החוצצים (ואז ממילא יקבעו מקומות של האחדות) ולכן יש [math]\displaystyle{ {n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!} }[/math] אפשריות כאלו.

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

הוכחה

נסמן את האיברים בקבוצה [math]\displaystyle{ a_1,...,a_n }[/math]. נסמן את מספר החזרות של כל איבר [math]\displaystyle{ a_i }[/math] ב-[math]\displaystyle{ x_i }[/math] (שלם אי שלילי). כיוון שרוצים לבחור k איברים השאלה שקולה ל-כמה פתרונות שלמים אי שליליים יש למשוואה [math]\displaystyle{ x_1+...+x_n=k }[/math] שראינו שהתשובה היא [math]\displaystyle{ {n+k-1\choose k} }[/math]

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

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

1. [math]\displaystyle{ {50 \choose 2}+{50 \choose 2} }[/math]

2. [math]\displaystyle{ {50 \choose 2}\cdot {50 \choose 2}+{50 \choose 2} }[/math]

3. [math]\displaystyle{ {50 \choose 2}\cdot 50! }[/math]

4. [math]\displaystyle{ {50+2-1 \choose 50-1} }[/math]

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

1. [math]\displaystyle{ {50 \choose 1}\cdot {50 \choose 2}+{50 \choose 3} }[/math]

2. [math]\displaystyle{ {50 \choose 2}\cdot {50 \choose 2}+{50 \choose 2} }[/math]

3. [math]\displaystyle{ {50 \choose 2+1}\cdot 3! }[/math]

4. [math]\displaystyle{ {50+3-1 \choose 50-1} }[/math]

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

פתרון.

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

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

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

ג. נסמן [math]\displaystyle{ |A|=a }[/math]. מספרים היחסים על A הוא קבוצת החזקה של [math]\displaystyle{ A\times A }[/math] שזה [math]\displaystyle{ 2^{|A\times A|}=2^{a^2} }[/math]. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה

[math]\displaystyle{ n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!} }[/math] איברים.

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

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

בעייה	מספר האפשרויות
מספר האפשרויות לסדר 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]

@@ שורה 94: / שורה 94: @@
 כעת, יש לנו <math>n+k-1</math> מקומות שצריך למלא (k אחדות ו n-1 חוצצים) וצריך לבחור מתוכם את המקומות של החוצצים (ואז ממילא יקבעו מקומות של האחדות) ולכן יש
 <math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math> אפשריות כאלו.
-אם כן, נספור את מספר האפשרויות לסדר את החוצצים. נשים בשורה את כל האחדות ואת כל החוצצים, סה"כ נקבל <math>n+k-1</math> איברים. מספר האפשרויות לסדר אותם הוא <math>(n+k-1)!</math>. כעת, צריך לחלק בחזרות המיותרות: סדר החוצצים אינו משנה, וכמו כן סדר האחדות אינו משנה. לכן סה"כ מספר האפשרויות הינו <math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math>
+'''מסקנה''' מספר הדרכים שיש לבחור k איברים מתוך קבוצה של n איברים כאשר מותר לי לבצע חזרות ולא משנה הסדר הוא <math>{n+k-1\choose k}</math>
-'''מסקנה''' מספר הדרכים שיש לבחור k איברים מתוך קבוצה של n איברים כאשר מותר לי לבצע חזרות ולא משנה לי סדר האיברים הוא <math>{n+k-1\choose k}</math>
 '''הוכחה'''
-נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר הפעמים ש<math>a_n</math> נבחר ב-<math>x_n</math> (שלם אי שלילי). כמובן שסכום <math>x_n</math> חייב להיות k.
+נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר החזרות של כל איבר <math>a_i</math>  ב-<math>x_i</math> (שלם אי שלילי).
+כיוון שרוצים לבחור k איברים השאלה שקולה ל-כמה פתרונות שלמים אי שליליים יש למשוואה <math>x_1+...+x_n=k</math> שראינו שהתשובה היא <math>{n+k-1\choose k}</math>
-בדוגמא לעיל נסמן <math>\{0,1\}=\{a_1,a_2\}</math>. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה <math>x_1+x_2=2+1=3</math>, וכדומה.
@@ שורה 136: / שורה 134: @@
 ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. <math>{50 \choose 3}+{50\choose 2}\cdot{50 \choose 1}</math>
-ג. נסמן <math>|A|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{|A\times A|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה <math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.
+ג. נסמן <math>|A|=a</math>. מספרים היחסים על A הוא קבוצת החזקה של <math>A\times A</math> שזה <math>2^{|A\times A|}=2^{a^2}</math>. כעת, פונקציה חד ערכית מקבוצה בגודל k אל קבוצה בגודל n מכילה
+ <math>n\cdot (n-1) \cdots (n-k+1)=\frac{n!}{(n-k)!}</math> איברים.
 אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.