|}
נתחיל לטפל בכל אחד מהמקרים:
=== יש חשיבות לסדר ויש חזרות ===
בהנתן 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> מקומות שצריך למלא (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 איברים כאשר מותר לי לבצע חזרות ולא משנה לי סדר האיברים? דבר ראשון נסביר את התרגיל. נגיד אנו רוצים לבחור 3 מספרים בינאריים כאשר לא חשוב לנו הסדר. אז אפשר לבחור הוא <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>\{0,1\}=\{a_1,a_2\}</math>. בחירת שני אחדות ואפס יחיד שקולה לפתרון המשוואה <math>x_1+x_2=2+1=3</math>, וכדומה.