שינויים

קפיצה אל: ניווט, חיפוש

תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג

הוסרו 45 בתים, 13:41, 3 בפברואר 2013
/* פונקציות יוצרות */
* נרצה לחשב את <math>c_n:=\sum_{k=0}^n a_kb_{n-k}</math>. נגדיר <math>f_1(x)=\sum_{i=0}^\infty a_ix^i</math> ו־<math>f_2(x)=\sum_{i=0}^\infty b_ix^i</math> ולכן <math>f_1(x)f_2(x)=\sum_{i=0}^\infty c_i x^i</math>.
* נרצה למצוא את מספר הפתרונות של <math>\sum_{i=1}^k t_i=n</math> כאשר <math>\forall i:\ t_i\in A_i\subseteq\mathbb N_0</math>. נתאים לכל משתנה פונקציה יוצרת <math>f_i(x)=\sum_{t\in A_i} x^t</math> ולכן מספר הפתרונות הדרוש הוא המקדם של <math>x^n</math> ב־<math>\prod_{i=1}^k f_i(x)</math>.
* נרצה למצוא כמה דרכים יש לחלק חליפות עם חזרות קיימות של <math>n</math> כדורים שונים בין מתוך <math>k</math> תאים כאשר בתא ה־המספר <math>i</math> חייב להיות להופיע מספר כדורים פעמים השייך לקבוצה <math>A_i\subseteq\mathbb N_0</math> וסדר השמת הכדורים משנה. נתאים לכל תא מספר פונקציה <math>f_i(x)=\sum_{t\in A_i}\frac{x^t}{t!}</math> ולכן המספר הדרוש הוא הכמות הדרושה היא המקדם של <math>\frac{x^n}{n!}</math> ב־<math>\prod_{i=1}^k f_i(x)</math>.
* אם <math>X:A\to\{0,1,\dots,n\}</math> משתנה מקרי כש־<math>|A|<\infty</math> ו־<math>f(x)=\sum_{k=0}^n |X^{-1}[\{k\}]|x^k</math> אז <math>f(1)=|A|</math>, התוחלת היא <math>\mbox{E}(X)=\frac{f'(1)}{f(1)}</math> והשונות היא <math>\mbox{V}(X)=\frac{f''(1)}{f(1)}+\mbox{E}(X)-\mbox{E}^2(X)</math>.