* נסמן <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>F_n=\frac{5-\sqrt5}{10}\left(\frac{1-\sqrt5}2\right)^n+\frac2{5-\sqrt5}\left(\frac{1+\sqrt5}2\right)^n</math>.
* '''ריצוף דומינו''' של <math>A\subseteq\mathbb Z^2</math> הוא כיסוי של <math>A</math> על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־<math>A</math>.
:* ללוח בגודל <math>m\times n</math> קיים ריצוף דומינו אם״ם <math>mn</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>n</math>) על <math>[n]</math> כך שהמספרים עולים לאורך השורות העמודות.
:* <math>f(\boldsymbol\lambda)</math> היא מספר טבלאות יאנג שקיימות לדיאגרמת יאנג הנוצרת מהחלוקה <math>\boldsymbol\lambda</math>.
::* <math>f(n-k,\underbrace{1,1,\dots,1}_k)=\binom{n-1}k\ \and\ f(n,n)=C_n\ \and\ f(n-k,k)=\frac{n-2k+1}n\binom nk</math>.
::* '''נוסחת הווים:''' תהי <math>\boldsymbol\lambda</math> ונרצה לחשב את <math>f(\boldsymbol\lambda)</math>. לכל משבצת בדיאגרמת יאנג נתאים "אורך וו" (hook length) כמספר המשבצות באותה שורה או עמודה שאחרי המשבצת הנתונה ועוד 1. נסמן <math>\Pi</math> כמכפלת אורכי הווים של כל המשבצות. אזי <math>f(\boldsymbol\lambda)=\frac{n!}\Pi</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>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>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>.
* '''מספר סטירלינג מסוג 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>.
* <math>S_N=s_N^{-1}</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>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>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}(xX)=\frac{f'(1)}{f(1)}</math> והשונות היא <math>\mbox{V}(X)=\frac{f''(1)}{f(1)}+\mbox{E}(X)-\mbox{E}^2(X)</math>. === נוסחאות נסיגה ===* '''נוסחת נסיגה''' מסדר <math>k</math> היא נוסחה מהצורה <math>\forall n\ge k:\ a_n=f(a_{n-1},a_{n-2},\dots,a_{n-k})</math>.:* איברי סדרה המקיימת נוסחת נסיגה כזו נקבעים ע״י <math>k</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>(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_n=\sum_{i=1}^k c_i a_{n-i}</math> מסדר <math>k</math>. נניח שיש <math>t\in\mathbb C</math> עבורו <math>\forall n:\ a_n=t^n</math> (לא תמיד זה נכון). אזי <math>t=0</math> פתרון. <math>x^k-\sum_{i=1}^k c_i x^{k-i}</math> נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם <math>t\ne0</math> אז הוא שווה ל־0 בנקודה <math>t</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>\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>
* '''נוסחת נסיגה למספרי סטירלינג מסוג 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:\ \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>