שינויים
המשך יבוא
בתקציר זה, אלא אם צוין אחרת, כל המשתנים והנעלמים שלמים ואי־שליליים למעט <math>x,\alpha</math>. <math>p</math> ראשוני ו־<math>q</math> אינו שלם או אי־שלילי רק במקרים בהם הוא מוצג כמשתנה בפולינום. <math>\mathbb F</math> שדה.
* נסמן <math>[n]:=\{1,2,\dots,n\}=[1,n]\cap\mathbb N</math>. <math>S_n</math> היא קבוצת כל התמורות על <math>[n]</math>.
* '''חלוקת קבוצות''' של <math>A</math> ל־<math>n</math> היא בחירה של תתי־קבוצות <math>A_1,\dots,A_n\subseteq A</math> זרות עבורן <math>\biguplus_{k=1}^n A_k=A</math>.
* '''סדרת פיבונצ׳י''' תסומן <math>(F_n)_{n=0}^\infty</math>.
* '''ריצוף דומינו''' של <math>A\subseteq\mathbb Z^2</math> הוא כיסוי של <math>A</math> על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־<math>A</math>.
:* ללוח בגודל <math>m\times n</math> קיים ריצוף דומינו אם״ם <math>mn</math> זוגי.
:* ללוח בגודל <math>2\times n</math> קיימים <math>F_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>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>k</math>־יה סדורה של <math>k</math> איברים (לא דווקא שונים) מתוך <math>n</math>. יש <math>n^k</math> חליפות עם חזרות.
* '''צירוף:''' נניח <math>0\le k\le n</math>. צירוף של <math>k</math> איברים מתוך <math>n</math> הוא תת־קבוצה של קבוצה בת <math>n</math> איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא <math>C(n,k):=\binom nk</math>.
:* '''צירוף עם חזרות:''' הוא רב־קבוצה מסדר <math>k</math> של איברים מתוך קבוצה בת <math>n</math> איברים. יש <math>D(n,k):=\left(\!\!\!\binom nk\!\!\!\right):=\binom{n-1+k}k</math> צירופים עם חזרות.
::* מספר הצירופים עם חזרות של <math>k</math> מתוך <math>n</math> שווה למספר הדרכים לבחור <math>k</math> עצמים מתוך <math>n</math> סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־<math>\sum_{i=1}^n x_i=k</math>.
* '''הווקטור האופייני''' של קבוצה <math>A\subseteq [n]</math> מוגדר ע״י <math>\mathbf v_A:=(I_A(i))_{i=1}^n=\left(\begin{cases}1,&i\in A\\0,&i\not\in A\end{cases}\right)_{i=1}^n</math>.
* '''סדרה אונימוצלית''' היא סדרה <math>(a_i)_{i=1}^n</math> כך שקיים <math>k</math> עבורו <math>(a_i)_{i=1}^k</math> עולה במובן הרחב ו־<math>(a_i)_{i=k}^n</math> יורדת במובן הרחב.
:* <math>\Big(\tbinom ni\Big)_{i=0}^n</math> היא סדרה אונימוצלית כאשר אם <math>n</math> זוגי אז <math>k=n/2</math> ואחרת <math>k=\lfloor n/2\rfloor,\lceil n/2\rceil</math> (כי <math>\binom n{\lfloor n/2\rfloor}=\binom n{\lceil n/2\rceil}</math>).
* '''הפרת סדר''' בתמורה <math>\pi</math> היא זוג <math>i<j</math> כך ש־<math>\pi(j)<\pi(i)</math>. מספר הפרות הסדר מסומן <math>\mbox{inv}(\pi)</math> וסימן התמורה מוגדר כ־<math>\sgn(\pi):=(-1)^{\mbox{inv}(\pi)}</math>. התמרה <math>\pi</math> תקרא זוגית אם <math>\sgn(\pi)=1</math> ואי־זוגית אחרת. יש <math>n!/2</math> התמרות מכל סוג שסדרן <math>n</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>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>(1+x)^p\mod p=1+x^p</math>.
* '''משפט פרמה הקטן:''' <math>n^p\equiv n\pmod p</math>.
* '''פיתוח של מספר לפי ראשוני:''' נניח <math>p^d\le n</math> ו־<math>n<p^{d+1}</math>. אזי קיימים <math>a_0,\dots,a_d</math> שלמים כך ש־<math>\forall i:\ 0\le a_i<p</math> ו־<math>n=\sum_{i=0}^d a_ip^i</math>. סכום זה נקרא "הפיתוח של <math>n</math> לפי <math>p</math>".
* אם <math>n=2^d-1</math> אז <math>\forall 0\le k\le n:\ 2\nmid\binom nk</math>. לפיכך, <math>n=\sum_{i=0}^{d-1}2^i</math>.
* '''משפט לוקאס:''' נניח ש־<math>n=\sum_{i=0}^d a_i p^i</math> ו־<math>k=\sum_{i=0}^d b_i p^i</math> פיתוחים לפי <math>p</math>. אזי <math>\binom nk\equiv\prod_{i=0}^d\binom{a_i}{b_i}\pmod p</math>.
* <math>p\mid\binom nk</math> אם״ם בפיתוחים <math>n=\sum_{i=0}^d a_i p^i\ \and\ k=\sum_{i=0}^d b_i p^i</math> יש <math>i_0</math> עבורו <math>a_{i_0}<b_{i_0}</math>.
* '''פירוק/קומפוזיציה''' של <math>n</math> הוא הצגה של <math>n</math> כסכום של טבעיים.
:* יש <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]_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]_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>k</math> של מרחב וקטורי <math>\mathbb F^n</math> (כאשר ל־<math>\mathbb F</math> יש <math>q</math> איברים) הוא <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math>.
* אם <math>0\le k\le n</math> אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q\in\mathbb N_0[q]</math>, כלומר זה פולינום במשתנה <math>q</math> שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו <math>k(n-k)</math> והוא סימטרי (כלומר המקדם של <math>q^i</math> שווה למקדם של <math>q^{k(n-k)-i}</math> לכל <math>0\le i\le k(n-k)</math>).
* '''הילוך שריג''' הוא סדרת צעדים בין נקודות ב־<math>\mathbb Z^2</math> שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
:* יש <math>\binom{m+n}n</math> הילוכי שריג מ־<math>(0,0)</math> ל־<math>(m,n)</math>.
:* נסמן <math>C_t(m,n)</math> כמספר הילוכי השריג מ־<math>(0,0)</math> ל־<math>(m,n)</math> שהשטח המוגבל על־ידם, ציר ה־x והישר <math>x=m</math> הוא <math>t</math>. בנוסף, נגדיר <math>P_{m,n}(q)=\sum_{t=0}^{mn} C_t(m,n)q^t</math>. אזי <math>P_{m,n}(q)=\begin{bmatrix}m+n\\n\end{bmatrix}_q</math>.
* נסמן <math>I_n(q):=\sum_{\pi\in S_n}q^{\mbox{inv}(\pi)}</math>. אזי <math>I_n(q)=[n]_q!</math>.
* יהי <math>\mathbf v=(v_i)_{i=1}^n\in\mathbb Z_2^n</math> וקטור שרכיביו אפסים ואחדות. אם <math>i<j</math> ו־<math>v_i>v_j</math> נכנה זאת הפרת סדר. אם נסמן <math>I_{n,k}(q)=\sum_{\mathbf v\in\mathbb Z_2^n\ \and\ |\{i:\ v_i=1\}|=k}q^{\mbox{inv}(\mathbf v)}</math> אז <math>I_{n,k}(q)=\begin{bmatrix}n\\k\end{bmatrix}_q</math>.
* '''חלוקה''' של <math>n</math> היא וקטור <math>\boldsymbol\lambda=(\lambda_1,\dots,\lambda_k)</math> שסכום רכיביו הוא <math>n</math> (כלומר <math>\sum_{i=1}^k\lambda_i=n</math>) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן <math>p(n)</math>.
:* מספר החלוקות של <math>n</math> עם לכל היותר <math>k</math> רכיבים הוא המקדם של <math>q^n</math> בפולינום <math>\begin{bmatrix}n+k\\k\end{bmatrix}_q</math>, כלומר <math>C_n(n,k)</math>.
* '''דיאגרמת יאנג''' של חלוקה <math>(\lambda_1,\dots,\lambda_k)</math> היא דיאגרמת משבצות כך שבשורה ה־<math>i</math> יש <math>\lambda_i</math> משבצות המיושרות לשמאל.
* '''הילוכי דיק''' הם הילוכי שריג מ־<math>(0,0)</math> ל־<math>(n,n)</math> שנמצאים על ומעל הישר <math>x=y</math>.
* '''מספר קטלן''' הוא מספר הילוכי דיק ל־<math>(n,n)</math>, מסומן <math>C_n</math> ושווה ל־<math>\frac1{n+1}\binom{2n}n</math>.
:* נניח ש־<math>0<a<b</math>. יש <math>\frac{b-a}{b+a}\binom{a+b}a</math> הילוכי דיק ל־<math>(a,b)</math> שאינם עוברים על הישר <math>x=y</math> למעט בנקודה <math>(0,0)</math>.
:* '''מילת דיק''' מאורך <math>2n</math> היא סדרה <math>(a_i)_{i=1}^{2n}</math> כך ש־<math>\forall i:\ a_i\in\{\pm1\}</math>, <math>\forall k:\ \sum_{i=1}^k a_i\ge0</math> ו־<math>\sum_{i=1}^{2n}a_i=0</math>. יש <math>C_n</math> מילות דיק מאורך <math>2n</math>.
:* '''עץ בינארי שלם/מלא''' הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש <math>C_n</math> עצים בינארים מלאים עם <math>n+1</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>B_n</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>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>.
* '''מספר סטיכלינג הלא מסומן מסוג I''' הוא מספר התמורות על <math>[n]</math> עם <math>k</math> מחזורים ומסומן <math>C(n,k)</math>.
:* <math>n!=\sum_{k=1}^n C(n,k)</math>.
:* <math>C(n,n)=1\ \and\ C(n,1)=(n-1)!</math>.
* '''מספר סטיכלינג מסוג I''' הוא <math>s(n,k):=(-1)^{n-k}C(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>S_N=s_N^{-1}</math>.
=== פונקציות יוצרות ===
* טור חזקות פורמלי במשתנה <math>x</math> מכל <math>\mathbb F</math> (בד״כ <math>\mathbb Q,\mathbb R,\mathbb C</math>) הוא ביטוי מהצורה <math>\sum_{i=0}^\infty a_ix^i</math> כאשר <math>\forall i:\ a_i\in\mathbb F</math>. הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־<math>x</math> מעל <math>\mathbb F</math> מסומן <math>\mathbb F[[x]]</math>.
:* אם <math>\exists n_0:\ \forall i>n_0:\ a_i=0</math> אז הטור הוא פולינום. אוסף הפולינומים ב־<math>x</math> מעל <math>\mathbb F</math> מסומן <math>\mathbb F[x]</math>.
* '''נוסחת טיילור:''' אם <math>f(x)=\sum_{i=0}^\infty a_ix^i</math> אז <math>a_i=\frac{f^{(i)}(0)}{i!}x^i</math>.
* '''פונקציה יוצרת:''' לכל סדרה <math>(a_i)_{i=0}^\infty</math> נתאים פונקציה <math>\sum_{i=0}^\infty a_ix^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>\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>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>\binom nk=\binom{n-1}k+\binom{n-1}{k-1}</math>
* <math>\binom nk=\sum_{i=k}^n\binom{i-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\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>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>\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>
* '''נוסחת q־פסקל:''' <math>\begin{bmatrix}n\\k\end{bmatrix}_q=\begin{bmatrix}n-1\\k-1\end{bmatrix}_q+q^k\begin{bmatrix}n-1\\k\end{bmatrix}_q</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>0:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</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>
* '''נוסחת נסיגה למספרי סטיכלינג לא מסומנים מסוג 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>
* <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>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math>
* נסמן <math>[n]:=\{1,2,\dots,n\}=[1,n]\cap\mathbb N</math>. <math>S_n</math> היא קבוצת כל התמורות על <math>[n]</math>.
* '''חלוקת קבוצות''' של <math>A</math> ל־<math>n</math> היא בחירה של תתי־קבוצות <math>A_1,\dots,A_n\subseteq A</math> זרות עבורן <math>\biguplus_{k=1}^n A_k=A</math>.
* '''סדרת פיבונצ׳י''' תסומן <math>(F_n)_{n=0}^\infty</math>.
* '''ריצוף דומינו''' של <math>A\subseteq\mathbb Z^2</math> הוא כיסוי של <math>A</math> על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־<math>A</math>.
:* ללוח בגודל <math>m\times n</math> קיים ריצוף דומינו אם״ם <math>mn</math> זוגי.
:* ללוח בגודל <math>2\times n</math> קיימים <math>F_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>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>k</math>־יה סדורה של <math>k</math> איברים (לא דווקא שונים) מתוך <math>n</math>. יש <math>n^k</math> חליפות עם חזרות.
* '''צירוף:''' נניח <math>0\le k\le n</math>. צירוף של <math>k</math> איברים מתוך <math>n</math> הוא תת־קבוצה של קבוצה בת <math>n</math> איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא <math>C(n,k):=\binom nk</math>.
:* '''צירוף עם חזרות:''' הוא רב־קבוצה מסדר <math>k</math> של איברים מתוך קבוצה בת <math>n</math> איברים. יש <math>D(n,k):=\left(\!\!\!\binom nk\!\!\!\right):=\binom{n-1+k}k</math> צירופים עם חזרות.
::* מספר הצירופים עם חזרות של <math>k</math> מתוך <math>n</math> שווה למספר הדרכים לבחור <math>k</math> עצמים מתוך <math>n</math> סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־<math>\sum_{i=1}^n x_i=k</math>.
* '''הווקטור האופייני''' של קבוצה <math>A\subseteq [n]</math> מוגדר ע״י <math>\mathbf v_A:=(I_A(i))_{i=1}^n=\left(\begin{cases}1,&i\in A\\0,&i\not\in A\end{cases}\right)_{i=1}^n</math>.
* '''סדרה אונימוצלית''' היא סדרה <math>(a_i)_{i=1}^n</math> כך שקיים <math>k</math> עבורו <math>(a_i)_{i=1}^k</math> עולה במובן הרחב ו־<math>(a_i)_{i=k}^n</math> יורדת במובן הרחב.
:* <math>\Big(\tbinom ni\Big)_{i=0}^n</math> היא סדרה אונימוצלית כאשר אם <math>n</math> זוגי אז <math>k=n/2</math> ואחרת <math>k=\lfloor n/2\rfloor,\lceil n/2\rceil</math> (כי <math>\binom n{\lfloor n/2\rfloor}=\binom n{\lceil n/2\rceil}</math>).
* '''הפרת סדר''' בתמורה <math>\pi</math> היא זוג <math>i<j</math> כך ש־<math>\pi(j)<\pi(i)</math>. מספר הפרות הסדר מסומן <math>\mbox{inv}(\pi)</math> וסימן התמורה מוגדר כ־<math>\sgn(\pi):=(-1)^{\mbox{inv}(\pi)}</math>. התמרה <math>\pi</math> תקרא זוגית אם <math>\sgn(\pi)=1</math> ואי־זוגית אחרת. יש <math>n!/2</math> התמרות מכל סוג שסדרן <math>n</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>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>(1+x)^p\mod p=1+x^p</math>.
* '''משפט פרמה הקטן:''' <math>n^p\equiv n\pmod p</math>.
* '''פיתוח של מספר לפי ראשוני:''' נניח <math>p^d\le n</math> ו־<math>n<p^{d+1}</math>. אזי קיימים <math>a_0,\dots,a_d</math> שלמים כך ש־<math>\forall i:\ 0\le a_i<p</math> ו־<math>n=\sum_{i=0}^d a_ip^i</math>. סכום זה נקרא "הפיתוח של <math>n</math> לפי <math>p</math>".
* אם <math>n=2^d-1</math> אז <math>\forall 0\le k\le n:\ 2\nmid\binom nk</math>. לפיכך, <math>n=\sum_{i=0}^{d-1}2^i</math>.
* '''משפט לוקאס:''' נניח ש־<math>n=\sum_{i=0}^d a_i p^i</math> ו־<math>k=\sum_{i=0}^d b_i p^i</math> פיתוחים לפי <math>p</math>. אזי <math>\binom nk\equiv\prod_{i=0}^d\binom{a_i}{b_i}\pmod p</math>.
* <math>p\mid\binom nk</math> אם״ם בפיתוחים <math>n=\sum_{i=0}^d a_i p^i\ \and\ k=\sum_{i=0}^d b_i p^i</math> יש <math>i_0</math> עבורו <math>a_{i_0}<b_{i_0}</math>.
* '''פירוק/קומפוזיציה''' של <math>n</math> הוא הצגה של <math>n</math> כסכום של טבעיים.
:* יש <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]_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]_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>k</math> של מרחב וקטורי <math>\mathbb F^n</math> (כאשר ל־<math>\mathbb F</math> יש <math>q</math> איברים) הוא <math>\begin{bmatrix}n\\k\end{bmatrix}_q</math>.
* אם <math>0\le k\le n</math> אז <math>\begin{bmatrix}n\\k\end{bmatrix}_q\in\mathbb N_0[q]</math>, כלומר זה פולינום במשתנה <math>q</math> שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו <math>k(n-k)</math> והוא סימטרי (כלומר המקדם של <math>q^i</math> שווה למקדם של <math>q^{k(n-k)-i}</math> לכל <math>0\le i\le k(n-k)</math>).
* '''הילוך שריג''' הוא סדרת צעדים בין נקודות ב־<math>\mathbb Z^2</math> שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
:* יש <math>\binom{m+n}n</math> הילוכי שריג מ־<math>(0,0)</math> ל־<math>(m,n)</math>.
:* נסמן <math>C_t(m,n)</math> כמספר הילוכי השריג מ־<math>(0,0)</math> ל־<math>(m,n)</math> שהשטח המוגבל על־ידם, ציר ה־x והישר <math>x=m</math> הוא <math>t</math>. בנוסף, נגדיר <math>P_{m,n}(q)=\sum_{t=0}^{mn} C_t(m,n)q^t</math>. אזי <math>P_{m,n}(q)=\begin{bmatrix}m+n\\n\end{bmatrix}_q</math>.
* נסמן <math>I_n(q):=\sum_{\pi\in S_n}q^{\mbox{inv}(\pi)}</math>. אזי <math>I_n(q)=[n]_q!</math>.
* יהי <math>\mathbf v=(v_i)_{i=1}^n\in\mathbb Z_2^n</math> וקטור שרכיביו אפסים ואחדות. אם <math>i<j</math> ו־<math>v_i>v_j</math> נכנה זאת הפרת סדר. אם נסמן <math>I_{n,k}(q)=\sum_{\mathbf v\in\mathbb Z_2^n\ \and\ |\{i:\ v_i=1\}|=k}q^{\mbox{inv}(\mathbf v)}</math> אז <math>I_{n,k}(q)=\begin{bmatrix}n\\k\end{bmatrix}_q</math>.
* '''חלוקה''' של <math>n</math> היא וקטור <math>\boldsymbol\lambda=(\lambda_1,\dots,\lambda_k)</math> שסכום רכיביו הוא <math>n</math> (כלומר <math>\sum_{i=1}^k\lambda_i=n</math>) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן <math>p(n)</math>.
:* מספר החלוקות של <math>n</math> עם לכל היותר <math>k</math> רכיבים הוא המקדם של <math>q^n</math> בפולינום <math>\begin{bmatrix}n+k\\k\end{bmatrix}_q</math>, כלומר <math>C_n(n,k)</math>.
* '''דיאגרמת יאנג''' של חלוקה <math>(\lambda_1,\dots,\lambda_k)</math> היא דיאגרמת משבצות כך שבשורה ה־<math>i</math> יש <math>\lambda_i</math> משבצות המיושרות לשמאל.
* '''הילוכי דיק''' הם הילוכי שריג מ־<math>(0,0)</math> ל־<math>(n,n)</math> שנמצאים על ומעל הישר <math>x=y</math>.
* '''מספר קטלן''' הוא מספר הילוכי דיק ל־<math>(n,n)</math>, מסומן <math>C_n</math> ושווה ל־<math>\frac1{n+1}\binom{2n}n</math>.
:* נניח ש־<math>0<a<b</math>. יש <math>\frac{b-a}{b+a}\binom{a+b}a</math> הילוכי דיק ל־<math>(a,b)</math> שאינם עוברים על הישר <math>x=y</math> למעט בנקודה <math>(0,0)</math>.
:* '''מילת דיק''' מאורך <math>2n</math> היא סדרה <math>(a_i)_{i=1}^{2n}</math> כך ש־<math>\forall i:\ a_i\in\{\pm1\}</math>, <math>\forall k:\ \sum_{i=1}^k a_i\ge0</math> ו־<math>\sum_{i=1}^{2n}a_i=0</math>. יש <math>C_n</math> מילות דיק מאורך <math>2n</math>.
:* '''עץ בינארי שלם/מלא''' הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש <math>C_n</math> עצים בינארים מלאים עם <math>n+1</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>B_n</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>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>.
* '''מספר סטיכלינג הלא מסומן מסוג I''' הוא מספר התמורות על <math>[n]</math> עם <math>k</math> מחזורים ומסומן <math>C(n,k)</math>.
:* <math>n!=\sum_{k=1}^n C(n,k)</math>.
:* <math>C(n,n)=1\ \and\ C(n,1)=(n-1)!</math>.
* '''מספר סטיכלינג מסוג I''' הוא <math>s(n,k):=(-1)^{n-k}C(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>S_N=s_N^{-1}</math>.
=== פונקציות יוצרות ===
* טור חזקות פורמלי במשתנה <math>x</math> מכל <math>\mathbb F</math> (בד״כ <math>\mathbb Q,\mathbb R,\mathbb C</math>) הוא ביטוי מהצורה <math>\sum_{i=0}^\infty a_ix^i</math> כאשר <math>\forall i:\ a_i\in\mathbb F</math>. הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־<math>x</math> מעל <math>\mathbb F</math> מסומן <math>\mathbb F[[x]]</math>.
:* אם <math>\exists n_0:\ \forall i>n_0:\ a_i=0</math> אז הטור הוא פולינום. אוסף הפולינומים ב־<math>x</math> מעל <math>\mathbb F</math> מסומן <math>\mathbb F[x]</math>.
* '''נוסחת טיילור:''' אם <math>f(x)=\sum_{i=0}^\infty a_ix^i</math> אז <math>a_i=\frac{f^{(i)}(0)}{i!}x^i</math>.
* '''פונקציה יוצרת:''' לכל סדרה <math>(a_i)_{i=0}^\infty</math> נתאים פונקציה <math>\sum_{i=0}^\infty a_ix^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>\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>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>\binom nk=\binom{n-1}k+\binom{n-1}{k-1}</math>
* <math>\binom nk=\sum_{i=k}^n\binom{i-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\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>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>\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>
* '''נוסחת q־פסקל:''' <math>\begin{bmatrix}n\\k\end{bmatrix}_q=\begin{bmatrix}n-1\\k-1\end{bmatrix}_q+q^k\begin{bmatrix}n-1\\k\end{bmatrix}_q</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>0:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}</math> ו־<math>B_0=1</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>
* '''נוסחת נסיגה למספרי סטיכלינג לא מסומנים מסוג 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>
* <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>\sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n}</math>
