'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
[[מדיה:11BdidaCombBG.pdf|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]
=מבוא לקומבינטוריקה=
[[מדיה:11BdidaCombBG.pdf|קובץ דוגמאות והסברים בקומבינטוריקה מבן גוריון]]
קומבינטוריקה הוא ענף במתמטיקה העוסק בספירת עצמים המקיימים תכונה מסוימת. לדוגמא, כמה תוצאות אפשריות שונות יש למשחקי הכדורגל (על מנת למלא טופס וינר).
== מספר האפשריות לבחור k עצמים מתוך n עצמים==
השאלות שצריך לשאול הם- האם יש חשיבות לסדר (הבחירה) והאם מותר לבחור איבר פעמיים. לכן ישנם 4 מקרים אפשריים.
נשים לב שאם אסור חזרות אזי חייב להיות <math>k\leq n</math> (אחרת התשובה היא 0)
{| border="1" align="center" style="text-align:center;"
כעת, יש לנו <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>
'''הוכחה'''
נסמן את האיברים בקבוצה <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>, וכדומה.
ב. ניתן לבחור שלושה מספרים זוגיים, או שני אי זוגיים וזוגי. <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.