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

אור שחף: /* נוסחאות נסיגה */

2013-10-09T13:06:07Z

נוסחאות נסיגה

→ הגרסה הקודמת		גרסה מ־13:06, 9 באוקטובר 2013
שורה 86:		שורה 86:
	:* '''נוסחת נסיגה לינארית''' מסדר <math>k</math> היא נוסחה מהצורה <math>\forall n\ge k:\ a_n=f(n)+\sum_{i=1}^k c_i(n)a_{n-i}</math>. אם <math>c_i</math> פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם <math>f(n)\equiv0</math> אז נאמר שהיא הומוגנית.		:* '''נוסחת נסיגה לינארית''' מסדר <math>k</math> היא נוסחה מהצורה <math>\forall n\ge k:\ a_n=f(n)+\sum_{i=1}^k c_i(n)a_{n-i}</math>. אם <math>c_i</math> פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם <math>f(n)\equiv0</math> אז נאמר שהיא הומוגנית.
	::* קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר <math>k</math> היא מרחב וקטורי ממימד <math>k</math>.		::* קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר <math>k</math> היא מרחב וקטורי ממימד <math>k</math>.
	* נרצה לחשב את אברי <math>(a_i)_{i=0}^\infty</math> בהינתן תנאי ההתחלה <math>(a_i)_{i=0}^{k-1}</math> ונוסחת נסיגה <math>\forall i\ge k:\ a_i=f(a_{i-1},\dots,a_{i-k})</math>. נעזר בפונקציה היוצרת <math>f(x)=\sum_{i=0}^\infty a_i x^i</math> ואם קיימת פונקציה <math>F</math> עבורה {{left\|<math>\begin{align}f(x)&=\sum_{i=0}^{k-1} a_i x^i+\sum_{i=k}^\infty f(a_{i-1},\dots,a_{i-k})x^i\\&=\sum_{i=0}^{k-1} a_i x^i+F\!\left(x,\sum_{i=k}^\infty a_{i-1}x^{i-1},\dots,\sum_{i=k}^\infty a_{i-k}x^{i-k}\right)\\&=\sum_{i=0}^{k-1} a_i x^i+F\!\left(x,f(x)-\sum_{i=0}^{k-2} a_ix^i,\dots,f(x)\right)\end{align}</math>}}אז נבודד את <math>f(x)</math> ונקבל נוסחה מפורשת למקדמים <math>a_i</math> של <math>x^i</math>.		* נרצה לחשב את אברי <math>(a_i)_{i=0}^\infty</math> בהינתן תנאי ההתחלה <math>(a_i)_{i=0}^{k-1}</math> ונוסחת נסיגה <math>\forall i\ge k:\ a_i=g(a_{i-1},\dots,a_{i-k})</math>. נעזר בפונקציה היוצרת <math>f(x)=\sum_{i=0}^\infty a_i x^i</math> ואם קיימת פונקציה <math>G</math> עבורה {{left\|<math>\begin{align}f(x)&=\sum_{i=0}^{k-1} a_i x^i+\sum_{i=k}^\infty g(a_{i-1},\dots,a_{i-k})x^i\\&=\sum_{i=0}^{k-1} a_i x^i+G\!\left(x,\sum_{i=k}^\infty a_{i-1}x^{i-1},\dots,\sum_{i=k}^\infty a_{i-k}x^{i-k}\right)\\&=\sum_{i=0}^{k-1} a_i x^i+G\!\left(x,f(x)-\sum_{i=0}^{k-2} a_ix^i,\dots,f(x)\right)\end{align}</math>}}אז נבודד את <math>f(x)</math> ונקבל נוסחה מפורשת למקדמים <math>a_i</math> של <math>x^i</math>.
	* תהי נוסחת נסיגה לינארית הומוגנית <math>a_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>\alpha\in\mathbb C</math> עבורו <math>\forall n:\ a_n=\alpha^n</math> (לא תמיד זה נכון). אזי <math>\alpha=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>\alpha\ne0</math> אז הוא שווה ל־0 בנקודה <math>\alpha</math>. יש לו <math>k</math> שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם <math>\alpha_1,\dots,\alpha_k</math> אז <math>\forall n,i:\ a_n=\alpha_i^n</math>. המרחב הווקטורי של הפתרונות הוא אם כן <math>\left\{\left(\sum_{i=1}^k r_i\alpha_i^n\right)_{n=0}^\infty:\ \forall i:\ r_i\in\mathbb C\right\}</math>. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־<math>r_i</math>־ים.		* תהי נוסחת נסיגה לינארית הומוגנית עם מקדמים קבועים <math>a_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>\alpha\in\mathbb C</math> עבורו <math>\forall n:\ a_n=\alpha^n</math> (לא תמיד זה נכון). אזי <math>\alpha=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>\alpha\ne0</math> אז הוא שווה ל־0 בנקודה <math>\alpha</math>. יש לו <math>k</math> שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם <math>\alpha_1,\dots,\alpha_k</math> אז <math>\forall n,i:\ a_n=\alpha_i^n</math>. המרחב הווקטורי של הפתרונות הוא אם כן <math>\left\{\left(\sum_{i=1}^k r_i\alpha_i^n\right)_{n=0}^\infty:\ \forall i:\ r_i\in\mathbb C\right\}</math>. אם נתונים תנאי ההתחלה ניתן גם לחשב את ה־<math>r_i</math>־ים.

	=== נוסחאות ===		=== נוסחאות ===

אור שחף ב־18:47, 29 ביולי 2013

2013-07-29T18:47:47Z

→ הגרסה הקודמת		גרסה מ־18:47, 29 ביולי 2013
שורה 33:		שורה 33:
	:* יש <math>2^{n-1}</math> פירוקים של <math>n</math> (כאשר יש חשיבות לסדר (<math>2+1</math> שונה מ־<math>1+2</math>) וחזרות מותרות (<math>1+1+1</math> ייספר כפירוק של 3)).		:* יש <math>2^{n-1}</math> פירוקים של <math>n</math> (כאשר יש חשיבות לסדר (<math>2+1</math> שונה מ־<math>1+2</math>) וחזרות מותרות (<math>1+1+1</math> ייספר כפירוק של 3)).
	* '''מקדם מולטינומי:''' מספר המילים מאורך <math>n</math> שבהן המספר <math>i</math> מופיע <math>n_i</math> פעמים (<math>\sum_i n_i=n</math>) הוא <math>\binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right.</math>.		* '''מקדם מולטינומי:''' מספר המילים מאורך <math>n</math> שבהן המספר <math>i</math> מופיע <math>n_i</math> פעמים (<math>\sum_i n_i=n</math>) הוא <math>\binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right.</math>.
	* {{הערה\|סימונים:}} <math>[n]_q:=\sum_{i=0}^{q-1}q^i</math>. כמו כן, <math>[n]_q!:=\prod_{i=1}^n [i]_q,\ [0]_q!=1</math> ו־<math>\forall 0\le k\le n:\ \begin{bmatrix}n\\k\end{bmatrix}_q:=\frac{[n]_q!}{[k]_q![n-k]_q!}</math>. ניתן להראות ש־<math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> שלם.		* {{הערה\|סימונים:}} <math>[n]_q:=\sum_{i=0}^{n-1}q^i</math>. כמו כן, <math>[n]_q!:=\prod_{i=1}^n [i]_q,\ [0]_q!=1</math> ו־<math>\forall 0\le k\le n:\ \begin{bmatrix}n\\k\end{bmatrix}_q:=\frac{[n]_q!}{[k]_q![n-k]_q!}</math>. ניתן להראות ש־<math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> שלם.
	:* <math>[n]_1=n</math> ו־<math>\forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1}</math>.		:* <math>[n]_1=n</math> ו־<math>\forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1}</math>.
	:* אם <math>q</math> זוגי אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> אי־זוגי.		:* אם <math>q</math> זוגי אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math> אי־זוגי.

אור שחף ב־11:30, 8 ביוני 2013

2013-06-08T11:30:30Z

→ הגרסה הקודמת		גרסה מ־11:30, 8 ביוני 2013
שורה 8:		שורה 8:
	:* ללוח בגודל <math>2\times n</math> קיימים <math>F_n</math> ריצופי דומינו.		:* ללוח בגודל <math>2\times n</math> קיימים <math>F_n</math> ריצופי דומינו.
	* '''עקרון שובך יונים:''' בחלוקה של קבוצה סופית <math>A</math> ל־<math>n</math> יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות <math>\|A\|/n</math>.		* '''עקרון שובך יונים:''' בחלוקה של קבוצה סופית <math>A</math> ל־<math>n</math> יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות <math>\|A\|/n</math>.
	* {{הערה\|סימונים:}} <math>(\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i)</math>~~. לכן~~ <math>(n)_k=\begin{cases}\frac{n!}{(n-k)!},&k\le n\\0,&\text{else}\end{cases}</math>. בנוסף, <math>\binom nk:=\begin{cases}\frac{n!}{k!(n-k)!},&0\le k\le n\\0,&\text{else}\end{cases}</math> ו־<math>\binom\alpha n:=\frac{(\alpha)_n}{n!}</math>.		* {{הערה\|סימונים:}} <math>(\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i)</math> ו־<math>(n)_k=\begin{cases}\frac{n!}{(n-k)!},&k\le n\\0,&\text{else}\end{cases}</math>. בנוסף, <math>\binom nk:=\begin{cases}\frac{n!}{k!(n-k)!},&0\le k\le n\\0,&\text{else}\end{cases}</math> ו־<math>\binom\alpha k:=\frac{(\alpha)_k}{k!}</math>.
	* '''חליפה:''' נניח <math>0\le k\le n</math>. חליפה של <math>k</math> איברים מתוך <math>n</math> היא <math>k</math>־יה סדורה של איברים שונים מקבוצה בת <math>n</math> איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא <math>P(n,k):=(n)_k</math>.		* '''חליפה:''' נניח <math>0\le k\le n</math>. חליפה של <math>k</math> איברים מתוך <math>n</math> היא <math>k</math>־יה סדורה של איברים שונים מקבוצה בת <math>n</math> איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא <math>P(n,k):=(n)_k</math>.
	:* '''תמורה''' היא חליפה של <math>n</math> מתוך <math>n</math>, ומספר התמורות הוא <math>P(n):=(n)_n=n!</math>.		:* '''תמורה''' היא חליפה של <math>n</math> מתוך <math>n</math>, ומספר התמורות הוא <math>P(n):=(n)_n=n!</math>.

אור שחף: /* נוסחאות */

2013-06-02T20:35:25Z

נוסחאות

אור שחף: /* נוסחאות */

2013-06-02T18:15:28Z

נוסחאות

→ הגרסה הקודמת		גרסה מ־18:15, 2 ביוני 2013
שורה 110:		שורה 110:
	* '''q־בינום:''' <math>\prod_{i=0}^{n-1}(1+q^ix)=\sum_{k=0}^n q^\binom k2\begin{bmatrix}n\\k\end{bmatrix}_q x^k</math>		* '''q־בינום:''' <math>\prod_{i=0}^{n-1}(1+q^ix)=\sum_{k=0}^n q^\binom k2\begin{bmatrix}n\\k\end{bmatrix}_q x^k</math>
	* '''נוסחת נסיגה למספרי קטלן:''' <math>\forall n>1:\ C_n=\sum_{i=1}^{n-1}C_i C_{n-i}</math> ו־<math>C_0=C_1=1</math>		* '''נוסחת נסיגה למספרי קטלן:''' <math>\forall n>1:\ C_n=\sum_{i=1}^{n-1}C_i C_{n-i}</math> ו־<math>C_0=C_1=1</math>
	* '''נוסחת נסיגה למספרי בל:''' <math>\forall n>0:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</math>		* '''נוסחת נסיגה למספרי בל:''' <math>\forall n>0:\ B_n=\sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</math>
	* '''נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k)</math> ו־<math>C(0,0)=1\ \and\ \forall n<k:\ C(n,k)=0\ \and\ \forall n>0:\ C(n,0)=0</math>		* '''נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k)</math> ו־<math>C(0,0)=1\ \and\ \forall n<k:\ C(n,k)=0\ \and\ \forall n>0:\ C(n,0)=0</math>
	* '''נוסחת נסיגה למספרי סטירלינג מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)</math>		* '''נוסחת נסיגה למספרי סטירלינג מסוג I:''' <math>\forall n\in\mathbb N,k\in[n]:\ s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)</math>

אור שחף ב־19:14, 3 בפברואר 2013

2013-02-03T19:14:57Z

→ הגרסה הקודמת		גרסה מ־19:14, 3 בפברואר 2013
שורה 21:		שורה 21:
	* '''מורד:''' עבור <math>\pi\in S_n</math> נקרא ל־<math>i</math> מורָד (descent) אם <math>\pi(i)>\pi(i+1)</math>. קבוצת המורדות תסומן <math>\mbox{Des}(\pi)</math>.		* '''מורד:''' עבור <math>\pi\in S_n</math> נקרא ל־<math>i</math> מורָד (descent) אם <math>\pi(i)>\pi(i+1)</math>. קבוצת המורדות תסומן <math>\mbox{Des}(\pi)</math>.
	:* <math>\left\|\Big\{\pi\in S_n:\ \mbox{Des}(\pi)\subseteq\{k\}\Big\}\right\|=\binom nk</math>.		:* <math>\left\|\Big\{\pi\in S_n:\ \mbox{Des}(\pi)\subseteq\{k\}\Big\}\right\|=\binom nk</math>.
			* '''אי־סדר מלא''' הוא תמורה <math>\pi\in S_n</math> כך ש־<math>\forall i:\ \pi(i)\ne i</math>. קבוצת האי־סדרים המלאים ב־<math>S_n</math> מסומנת <math>D_n</math> ומקיימת <math>\|D_n\|=n!\sum_{i=0}^n\frac{(-1)^i}{i!}</math>.
	* אם <math>0<k<p</math> אז <math>p\mid\binom pk</math>.		* אם <math>0<k<p</math> אז <math>p\mid\binom pk</math>.
	* יהי פולינום <math>f(x)=\sum_{k=0}^n a_kx^k</math>. נסמן <math>(f\mod m)(x):=\sum_{k=0}^n(a_k\mod m)x^k</math>.		* יהי פולינום <math>f(x)=\sum_{k=0}^n a_kx^k</math>. נסמן <math>(f\mod m)(x):=\sum_{k=0}^n(a_k\mod m)x^k</math>.

אור שחף: /* פונקציות יוצרות */

2013-02-03T15:40:55Z

פונקציות יוצרות

→ הגרסה הקודמת		גרסה מ־15:40, 3 בפברואר 2013
שורה 76:		שורה 76:
	* '''פונקציה יוצרת מעריכית:''' לכל סדרה <math>(a_i)_{i=0}^\infty</math> נתאים פונקציה <math>\sum_{i=0}^\infty \frac{a_i}{i!}x^i</math>. פונקציות אלה שימושיות לספירת עצמים עבורם הסדר משנה.		* '''פונקציה יוצרת מעריכית:''' לכל סדרה <math>(a_i)_{i=0}^\infty</math> נתאים פונקציה <math>\sum_{i=0}^\infty \frac{a_i}{i!}x^i</math>. פונקציות אלה שימושיות לספירת עצמים עבורם הסדר משנה.
	* נרצה לחשב את <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>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>\sum_{i=1}^n t_i=k</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^k</math> ב־<math>\prod_{i=1}^n 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>k</math> מתוך <math>n</math> כאשר כל <math>i</math> חייב להופיע מספר פעמים השייך לקבוצה <math>A_i\subseteq\mathbb N_0</math>. נתאים לכל <math>i</math> פונקציה <math>f_i(x)=\sum_{t\in A_i}\frac{x^t}{t!}</math> ולכן הכמות הדרושה היא המקדם של <math>\frac{x^k}{k!}</math> ב־<math>\prod_{i=1}^n 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>.		* אם <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>.

אור שחף: /* פונקציות יוצרות */

2013-02-03T13:42:16Z

פונקציות יוצרות

→ הגרסה הקודמת		גרסה מ־13:42, 3 בפברואר 2013
שורה 77:		שורה 77:
	* נרצה לחשב את <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>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>\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>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>.		* אם <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>.

אור שחף: /* פונקציות יוצרות */

2013-02-03T13:41:50Z

פונקציות יוצרות

→ הגרסה הקודמת		גרסה מ־13:41, 3 בפברואר 2013
שורה 77:		שורה 77:
	* נרצה לחשב את <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>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>\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>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>.		* אם <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>.

אור שחף ב־12:57, 3 בפברואר 2013

2013-02-03T12:57:49Z

→ הגרסה הקודמת		גרסה מ־20:35, 2 ביוני 2013
שורה 94:		שורה 94:
	* '''זהות הקפטן:''' <math>k\binom nk=n\binom{n-1}{k-1}</math>		* '''זהות הקפטן:''' <math>k\binom nk=n\binom{n-1}{k-1}</math>
	* '''הבינום של ניוטון:''' <math>(1+x)^\alpha=\sum_{k=0}^n\binom\alpha k x^k</math>		* '''הבינום של ניוטון:''' <math>(1+x)^\alpha=\sum_{k=0}^n\binom\alpha k x^k</math>
	* אם <math>1\le m\le k\le n~~</math> אז <math>~~\binom nk\binom km=\binom nm\binom{n-m}{k-m}</math>		* <math>\forall 0\le m\le k\le n:\ \binom nk\binom km=\binom nm\binom{n-m}{k-m}</math>
	* <math>\sum_{k=0}^n\binom nk=2^n</math>		* <math>\sum_{k=0}^n\binom nk=2^n</math>
	* <math>\sum_{2\mid k}\binom nk=\sum_{2\nmid k}\binom nk=2^{n-1}</math>		* <math>\sum_{2\mid k}\binom nk=\sum_{2\nmid k}\binom nk=2^{n-1}</math>
	* <math>\sum_{k=0}^n\binom nk^2=\binom{2n}n</math>		* <math>\sum_{k=0}^n\binom nk^2=\binom{2n}n</math>
	* <math>\sum_{k=0}^n k\binom nk=2^{n-1}n</math>		* <math>\sum_{k=0}^n k\binom nk=2^{n-1}n</math>
	* אם <math>8\mid n~~</math> אז <math>~~\sum_{4\mid k}\binom nk=2^{n-2}+2^{n/2-1}</math>		* <math>\forall 8\mid n:\ \sum_{4\mid k}\binom nk=2^{n-2}+2^{n/2-1}</math>
	* <math>\sum_{\sum_{i=1}^k n_i=n}\binom n{n_1,\dots,n_k}=k^n</math>		* <math>\sum_{\sum_{i=1}^k n_i=n}\binom n{n_1,\dots,n_k}=k^n</math>
	* <math>\binom n{n_1,\dots,n_k}=\prod_{i=1}^k\binom {n-\sum_{j=1}^{i-1} n_j}{n_i}</math>		* <math>\binom n{n_1,\dots,n_k}=\prod_{i=1}^k\binom {n-\sum_{j=1}^{i-1} n_j}{n_i}</math>
	* '''נוסחת המולטינום:''' <math>\left(\sum_{i=1}^k x_i\right)^n=\sum_{\sum_{i=1}^k n_i=n}\binom n{n_1,\dots,n_k}\prod_{i=1}^k x_i^{n_i}</math>		* '''נוסחת המולטינום:''' <math>\left(\sum_{i=1}^k x_i\right)^n=\sum_{\sum_{i=1}^k n_i=n}\binom n{n_1,\dots,n_k}\prod_{i=1}^k x_i^{n_i}</math>
	* <math>\binom n{n_1,\dots,n_k}=\sum_{i=1}^k\binom{n-1}{n_1,\dots,n_{i-1},n_i-1,n_{i+1},\dots,n_k}</math>		* <math>\binom n{n_1,\dots,n_k}=\sum_{i=1}^k\binom{n-1}{n_1,\dots,n_{i-1},n_i-1,n_{i+1},\dots,n_k}</math>
	* <math>\begin{bmatrix}n\\k\end{bmatrix}_q=\prod_{i=1}^k\frac{q^{n-k+i}-1}{q^i-1}</math>		* <math>\forall q>1:\ \begin{bmatrix}n\\k\end{bmatrix}_q=\prod_{i=1}^k\frac{q^{n-k+i}-1}{q^i-1}</math>
	* <math>\begin{bmatrix}n\\k\end{bmatrix}_q=\begin{bmatrix}n\\n-k\end{bmatrix}_q</math>		* <math>\begin{bmatrix}n\\k\end{bmatrix}_q=\begin{bmatrix}n\\n-k\end{bmatrix}_q</math>
	* <math>\begin{bmatrix}n\\k\end{bmatrix}_1=\binom nk</math>		* <math>\begin{bmatrix}n\\k\end{bmatrix}_1=\binom nk</math>
שורה 115:		שורה 115:
	* '''נוסחת נסיגה למספרי סטירלינג מסוג II:''' <math>\forall n\in\mathbb N,k\in[n]:\ S(n,k)=S(n-1,k-1)+k S(n-1,k)</math> ו־<math>S(0,0)=1\ \and\ \forall n<k:\ s(n,k)=0\ \and\ \forall n>0:\ S(n,0)=0</math>		* '''נוסחת נסיגה למספרי סטירלינג מסוג II:''' <math>\forall n\in\mathbb N,k\in[n]:\ S(n,k)=S(n-1,k-1)+k S(n-1,k)</math> ו־<math>S(0,0)=1\ \and\ \forall n<k:\ s(n,k)=0\ \and\ \forall n>0:\ S(n,0)=0</math>
	* <math>\binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n</math>		* <math>\binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n</math>
	* <math>\forall n~~\in\mathbb N~~:\ \binom{1/2}n=\frac{C_{n-1}}2\left(\frac{-1}4\right)^{n-1}</math>		* <math>\forall n>0:\ \binom{1/2}n=\frac{C_{n-1}}2\left(\frac{-1}4\right)^{n-1}</math>
	* <math>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math>		* <math>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math>

→ הגרסה הקודמת		גרסה מ־12:57, 3 בפברואר 2013
שורה 56:		שורה 56:
	:* בהינתן מכפלה לא אסוציאטיבית <math>x_1\cdot x_2\cdot\dots\cdot x_{n+1}</math> יש <math>C_n</math> דרכים להוסיף סוגריים.		:* בהינתן מכפלה לא אסוציאטיבית <math>x_1\cdot x_2\cdot\dots\cdot x_{n+1}</math> יש <math>C_n</math> דרכים להוסיף סוגריים.
	:* '''שילוש של מצולע משוכלל''' בעל <math>n</math> קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו <math>n-3</math> אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש <math>C_n</math> דרכים לשלש מצולע משוכלל בעל <math>n+2</math> צלעות.		:* '''שילוש של מצולע משוכלל''' בעל <math>n</math> קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו <math>n-3</math> אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש <math>C_n</math> דרכים לשלש מצולע משוכלל בעל <math>n+2</math> צלעות.
	* '''מספר בל''' הוא מספר חלוקות ~~הקבוצות של~~ <math>[n]</math> ומסומן <math>B_n</math>.		* '''מספר בל''' הוא מספר חלוקות הקבוצה <math>[n]</math> ומסומן <math>B_n</math>.
	* '''מספר סטירלינג הלא מסומן מסוג I''' הוא מספר התמורות על <math>[n]</math> עם <math>k</math> מחזורים ומסומן <math>C(n,k)</math>.		* '''מספר סטירלינג הלא מסומן מסוג I''' הוא מספר התמורות על <math>[n]</math> עם <math>k</math> מחזורים ומסומן <math>C(n,k)</math>.
	:* <math>n!=\sum_{k=1}^n C(n,k)</math>.		:* <math>n!=\sum_{k=1}^n C(n,k)</math>.
שורה 63:		שורה 63:
	:* יהי <math>N\in\mathbb N</math>. נסמן <math>s_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>s(n,k)</math>.		:* יהי <math>N\in\mathbb N</math>. נסמן <math>s_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>s(n,k)</math>.
	:* <math>\sum_{k=1}^n s(n,k)x^k=(x)_n</math>.		:* <math>\sum_{k=1}^n s(n,k)x^k=(x)_n</math>.
	* '''מספר סטירלינג מסוג II''' הוא מספר חלוקות ~~הקבוצות של~~ <math>[n]</math> ל־<math>k</math> תתי־קבוצות לא ריקות ומסומן <math>S(n,k)</math>.		* '''מספר סטירלינג מסוג II''' הוא מספר חלוקות הקבוצה <math>[n]</math> ל־<math>k</math> תתי־קבוצות לא ריקות ומסומן <math>S(n,k)</math>.
	:* <math>B_n=\sum_{k=1}^n S(n,k)</math>.		:* <math>B_n=\sum_{k=1}^n S(n,k)</math>.
	:* יהי <math>N\in\mathbb N</math>. נסמן <math>S_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>S(n,k)</math>.		:* יהי <math>N\in\mathbb N</math>. נסמן <math>S_N\in\mathbb R^{N\times N}</math> בתור המטריצה שהרכיב בשורה ה־<math>n</math> ובעמודה ה־<math>k</math> שלה הוא <math>S(n,k)</math>.
שורה 77:		שורה 77:
	* נרצה לחשב את <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>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>\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>k</math> כדורים שונים בין <math>n</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>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>.		* אם <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>.