קומבינטוריקה והסתברות - ארז שיינר

88-165 מבוא להסתברות וסטטיסטיקה

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

פלייליסט של כל הסרטונים בקומבינטוריקה

נוסחאות הבחירה

מבוא לנוסחאות הבחירה ודוגמא

• kמה פעמים מתוך nה?

בחירה עם סדר ועם חזרה

• עם סדר עם חזרה: $n^k$

• בחירה k פעמים מתוך n אפשרויות עם משמעות לסדר הבחירה ועם חזרות על הבחירה מוגדרת כפונקציה מקבוצת הבחירות אל קבוצת האפשרויות:
• $f:\{1,...,k\}\to \{1,...,n\}$

בחירה עם סדר ובלי חזרה

• עם סדר בלי חזרה: $\frac{n!}{(n-k)!}$

בחירה בלי סדר ובלי חזרה

• בלי סדר בלי חזרה: $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

בחירה בלי סדר ועם חזרה

• בלי סדר עם חזרה: $(\genfrac{}{}{0ex}{}{n-1+k}{k})=(\genfrac{}{}{0ex}{}{n-1+k}{n-1})=\frac{(n-1+k)!}{k!(n-1)!}$

הבינום של ניוטון ומקדמים מוליטינומיים

הבינום של ניוטון

• $(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$

• כמות תתי הקבוצות בגודל זוגי שווה לכמות תתי הקבוצות בגודל אי זוגי כי-
  • $0=((-1)+1{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^k$