שינויים
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
=מבוא לקומבינטוריקה=
[[מדיה:11BdidaCombBG.pdf|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]
קומבינטוריקה הוא ענף במתמטיקה העוסק בספירת עצמים המקיימים תכונה מסוימת. לדוגמא, כמה תוצאות אפשריות שונות יש למשחקי הכדורגל (על מנת למלא טופס וינר).
'''פתרון.''' למעשה בעייה זו שקולה לבעיית חלוקת 10 אנשים לשתי קבוצות שונות בלבד, מכיוון שיש רק דרך אחת למיין את האנשים לפי הסדר של התור המקורי בכל תת קבוצה. נלמד בהמשך כיצד לפתור בעייה פשוטה זו.
==מספר האפשרויות לסדר n עצמים שונים בשורה ==
'''דוגמא.''' בכמה דרכים אפשר לסדר n אנשים בתור?
'''פתרון.''' כל אחד יכול להיות ראשון בתור לכן כבר יש n אפשרויות. כעת, נניח ואיציק ראשון בתור, נותר לסדר n-1 אנשים אחריו בתור. נניח באינדוקציה שמספר האפשרויות לסדר n-1 אנשים בתור הוא <math>(n-1)!</math> ונקבל שמספר האפשרויות שלנו הוא <math>n\cdot (n-1)! = n!</math>.
== מספר האפשריות לבחור k עצמים מתוך n עצמים==
השאלות שצריך לשאול הם- האם יש חשיבות לסדר (הבחירה) והאם מותר לבחור איבר פעמיים. לכן ישנם 4 מקרים אפשריים.
נשים לב שאם אסור חזרות אזי חייב להיות <math>k\leq n</math> (אחרת התשובה היא 0)
{| border="1" align="center" style="text-align:center;"
|
|'''אין חזרות'''
|'''יש חזרות'''
|-
|''' יש חשיבות לסדר'''
|<math>\frac{n!}{(n-k)!}</math>
| <math>n^k</math>
|-
|'''אין חשיבות לסדר'''
|<math>\;\;\;{n \choose k} = \frac{n!}{k!(n-k)!} \;\;\;</math>
|<math>\;\;\;{n+k-1\choose k}\;\;\;</math>
|-
|}
נתחיל לטפל בכל אחד מהמקרים:
=== יש חשיבות לסדר ויש חזרות ===
בהנתן n עצמים אזי בבחירה הראשונה ניתן יש n אפשרויות לבחור ולבחירה השניה יש n אפשריות לבחור (כי מותר חזרות), ... ,לבחירה ה-k יש n אפשרויות לבחור ולכן בסה"כ יש <math>n^k</math> אפשרויות.
'''דוגמא''' כמה מספרים בינאריים יש עם 3 ספרות ?
''' פתרון''' לספרה הראשונה יש 2 אפשרויות, לספרה השניה יש 2 אפשרויות ולספרה השלישית יש 2 אפשריות ולכן בסה"כ יש <math>2^3</math> וזה כל המספרים. (הבחירה היא הספרות 0,1 כאשר מותר חזרות ויש חשיבות לסדר)
=== יש חשיבות לסדר ואין חזרות ===
נסדר את n החפצים בשורה וניקח את k הראשונים. ככה אנחנו מבטיחים שאין חזרות ויש חשיבות לסדר. דא עקא, בשיטה זו אנחנו מקבלים כפילויות.
כמה כפילויות יש לנו? במילים אחרות כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותרים. כיוון שאותם ניתן לסדר ב <math>(n-k)!</math> אפשרויות
נקבל שמספר האפשריות לבחירת k עצמים מתוך n עם חשיבות לסדר ובלי חזרות הוא <math>\frac{n!}{(n-k)!}</math>
'''דוגמא''' כמה מספרים בעלי 3 ספרות שונות יש?
''' פתרון''' נבחר מתוך הספרות 0-9 שלוש בחירות עם חשיבות לסדר ובלי חזרות ונקבל <math>\frac{10!}{(7)!}=10\cdot 9 \cdot 8</math> (לספרה הראשונה יש 10 אפשרויות, לספרה השניה יש רק 9 אפשרויות ולספרה האחרונה נשארו 8 אפשרויות)
=== אין חשיבות לסדר ואין חזרות ===
נבחר k עצמים עם חשיבות לסדר ובלי חזרות. כעת אם רוצים שלא יהיה חשיבות לסדר צריך לחלק בכל ה- <math>k!</math> אפשריות לסידור k איברים ולכן מספר האפשרויות לבחור k עצמים בלי חשיבות לסדר ובלי חזרות
הינו <math>\;\;\;{n \choose k} = \frac{n!}{k!(n-k)!} \;\;\;</math>
'''דוגמא.''' בכמה דרכים ניתן לבחור קבוצה של k חפצים מתוך קבוצה של n חפצים? (במילים אחרות, כמה תת קבוצות מעוצמת k יש לקבוצה מגודל n).
'''פתרון.''' זה שקול לבחור k חפצים כאשר הסדר לא משנה ובלי חזרות ולכן יש <math> {n \choose k} </math> תתי קבוצות.
'''פתרון''' לבחור קבוצה של k אברים שקול לבחור n-k אברים שאינם בקבוצה (כלומר לבחור תת קבוצה A זה כמו לבחור את המשלימה שלה)
{| border="1" align="center" style="text-align:center;"
|<math>n!</math>
|-
|מספר האפשרויות לבחור קבוצה של k תלמידים מתוך כיתה של n תלמידים'''(ללא משמעות לסדר, ללא חזרות)'''
|<math>{n \choose k} = \frac{n!}{k!(n-k)!}</math>
|-
|מספר האפשרויות לבנות סדרה עם k איברים מתוך קבוצה המכילה מ איברים'''(עם משמעות לסדר, ועם חזרות)'''
|<math>n^k</math>
|-
|מספר האפשרויות לבנות סדרה עם k איברים '''שונים''' מתוך קבוצה המכילה n איברים'''(עם משמעות לסדר, ללא חזרות)'''
|<math>\frac{n!}{(n-k)!}</math>
|-
|מספר האפשרויות לבחור k איברים מתוך n איברים '''(ללא משמעות לסדר, עם חזרות)'''
|<math>{n+k-1\choose k}=\frac{(n+k-1)!}{k!(n-1)!}</math>
|-
|}