'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
[[מדיה:11BdidaCombBG.pdf|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]
=מבוא לקומבינטוריקה=
[[מדיה: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 חפצים כאשר הסדר בינהם משנה, ולאחר מכן נחלק את הכמות שקיבלנו במספר האפשרויות לסדר את k החפצים (הלא הוא מסקנה: <math>\sum_{k=0}^n {n \choose k!}=2^n</math>).
אם כך, אנו מעוניינים לדעת כמה אפשרויות יש לנו לבחור k חפצים מתוך הוכחה: ניקח קבוצה X בת n חפצים כאשר הסדר שלהם משנה. נסדר את n החפצים בשורה וניקח את k הראשונים. כמה פעמים נקבל את אותה סדרת k חפצים? בדיוק כמספר הפעמים שאפשר לסדר את n-k החפצים הנותריםאיברים אזי שני האגפים שווים למספר הקבוצות של בקבוצת החזקה.
אם כך, קיבלנו נוסחא '''תרגיל''' הוכח כי <math>{n \choose k} = \frac{n!}{k!(\choose n-k)!}</math>
'''פתרון''' לבחור קבוצה של k אברים שקול לבחור n-k אברים שאינם בקבוצה (כלומר לבחור תת קבוצה A זה כמו לבחור את המשלימה שלה)
אתם מוזמנים גם לחשב ישירות.
=== אין חשיבות לסדר ויש חזרות ===
'''תרגיל.''' כמה פתרונות שלמים אי שליליים יש למשוואה <math>x_1+...+x_n=k</math>?
'''פתרון.''' נחלק את המספר <math>k =1+1+1\cdots+1</math> לאחדות, ונשים בין ונחלק את האחדות ל-n המשתנים האפשריים.נעשה זאת כך- נשים n-1 חוצצים שונים. המשתנה הבין n המשתנים ונחלק 1-s הוא מספר האחדות שבין החוצץ ים לפי כמות ה-s לקודמו1-ים שכל משתנה מקבל.
למשל נביט בפתרונות שונים למשוואה <math>x_1+x_2+x_3=2</math>:
אם כן, נספור את מספר האפשרויות לסדר את החוצצים. נשים בשורה את כל האחדות ואת כל החוצציםכעת, סה"כ נקבל יש לנו <math>n+k-1</math> איברים. מספר האפשרויות לסדר אותם הוא <math>מקומות שצריך למלא (k אחדות ו 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 איברים כאשר מותר לי לבצע חזרות ולא משנה לי סדר האיברים? דבר ראשון נסביר את התרגיל. נגיד אנו רוצים לבחור 3 מספרים בינאריים כאשר לא חשוב לנו הסדר. אז אפשר לבחור 1 אחד ושני אפסים, או שלושה אפסים, או שתי אחדות ואפס יחיד או שלושה אחדות. '''פתרון.הוכחה'''
נשים לב שזה תרגיל שקול לתרגיל הקודם. נקרא לאיברים נסמן את האיברים בקבוצה <math>a_1,...,a_n</math>. נסמן את מספר הפעמים שהחזרות של כל איבר <math>a_na_i</math> נבחר ב-<math>x_nx_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>, וכדומה.
א. ניתן לבחור כל מספר מ1 עד 100. כעת, המספר המתאים לו צריך להיות מאותה זוגיות על מנת שהסכום יהיה זוגי. לכן בבחירה הראשונה היו לנו 100 אפשרויות ובשנייה 49. כעת, סדר הזוג לא משנה לכן נחלק ב2. סה"כ התוצאה היא <math>50\cdot 49</math>. זה בדיוק שווה לסעיף 1, שכן
<math>{50 \choose 2}+{50 \choose 2}+=2{50 \choose 2} = 2\frac{50!}{2!48!}=2\frac{50\cdot 49}{2}</math>
ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. <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> איברים.
אבל, חייב להתקיים ש k<n אחרת לא תתכן פונקציה חח"ע (והנוסחא כמובן לא תהא הגיונית), במקרה שלנו <math>2^{a^2}>a</math> ולכן אין אף פונקציה חח"ע מקבוצת היחסים של A אל A.