שינויים

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

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

הוסרו 22 בתים, 20:35, 2 ביוני 2013
/* נוסחאות */
* '''זהות הקפטן:''' <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\forall 0\le m\le k\le n</math> אז <math>:\ \binom nk\binom km=\binom nm\binom{n-m}{k-m}</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_{k=0}^n\binom nk^2=\binom{2n}n</math>
* <math>\sum_{k=0}^n k\binom nk=2^{n-1}n</math>
* אם <math>\forall 8\mid n</math> אז <math>:\ \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>\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>\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>\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}_1=\binom nk</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>\forall n\in\mathbb 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>