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

בתקציר זה, אלא אם צוין אחרת, כל המשתנים והנעלמים שלמים ואי־שליליים למעט [math]\displaystyle{ x,\alpha }[/math]. [math]\displaystyle{ p }[/math] ראשוני ו־[math]\displaystyle{ q }[/math] אינו שלם או אי־שלילי רק במקרים בהם הוא מוצג כמשתנה בפולינום. [math]\displaystyle{ \mathbb F }[/math] שדה.

נסמן [math]\displaystyle{ [n]:=\{1,2,\dots,n\}=[1,n]\cap\mathbb N }[/math]. [math]\displaystyle{ S_n }[/math] היא קבוצת כל התמורות על [math]\displaystyle{ [n] }[/math].
חלוקת קבוצות של [math]\displaystyle{ A }[/math] ל־[math]\displaystyle{ n }[/math] היא בחירה של תתי־קבוצות [math]\displaystyle{ A_1,\dots,A_n\subseteq A }[/math] זרות עבורן [math]\displaystyle{ \biguplus_{k=1}^n A_k=A }[/math].
סדרת פיבונצ׳י תסומן [math]\displaystyle{ (F_n)_{n=0}^\infty }[/math] והיא מקיימת [math]\displaystyle{ 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]\displaystyle{ A\subseteq\mathbb Z^2 }[/math] הוא כיסוי של [math]\displaystyle{ A }[/math] על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־[math]\displaystyle{ A }[/math].

ללוח בגודל [math]\displaystyle{ m\times n }[/math] קיים ריצוף דומינו אם״ם [math]\displaystyle{ mn }[/math] זוגי.
ללוח בגודל [math]\displaystyle{ 2\times n }[/math] קיימים [math]\displaystyle{ F_n }[/math] ריצופי דומינו.

עקרון שובך יונים: בחלוקה של קבוצה סופית [math]\displaystyle{ A }[/math] ל־[math]\displaystyle{ n }[/math] יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות [math]\displaystyle{ |A|/n }[/math].
סימונים: [math]\displaystyle{ (\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i) }[/math] ו־[math]\displaystyle{ (n)_k=\begin{cases}\frac{n!}{(n-k)!},&k\le n\\0,&\text{else}\end{cases} }[/math]. בנוסף, [math]\displaystyle{ \binom nk:=\begin{cases}\frac{n!}{k!(n-k)!},&0\le k\le n\\0,&\text{else}\end{cases} }[/math] ו־[math]\displaystyle{ \binom\alpha k:=\frac{(\alpha)_k}{k!} }[/math].
חליפה: נניח [math]\displaystyle{ 0\le k\le n }[/math]. חליפה של [math]\displaystyle{ k }[/math] איברים מתוך [math]\displaystyle{ n }[/math] היא [math]\displaystyle{ k }[/math]־יה סדורה של איברים שונים מקבוצה בת [math]\displaystyle{ n }[/math] איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא [math]\displaystyle{ P(n,k):=(n)_k }[/math].

תמורה היא חליפה של [math]\displaystyle{ n }[/math] מתוך [math]\displaystyle{ n }[/math], ומספר התמורות הוא [math]\displaystyle{ P(n):=(n)_n=n! }[/math].
חליפה עם חזרות היא [math]\displaystyle{ k }[/math]־יה סדורה של [math]\displaystyle{ k }[/math] איברים (לא דווקא שונים) מתוך [math]\displaystyle{ n }[/math]. יש [math]\displaystyle{ n^k }[/math] חליפות עם חזרות.

צירוף: נניח [math]\displaystyle{ 0\le k\le n }[/math]. צירוף של [math]\displaystyle{ k }[/math] איברים מתוך [math]\displaystyle{ n }[/math] הוא תת־קבוצה של קבוצה בת [math]\displaystyle{ n }[/math] איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא [math]\displaystyle{ C(n,k):=\binom nk }[/math].

צירוף עם חזרות: הוא רב־קבוצה מסדר [math]\displaystyle{ k }[/math] של איברים מתוך קבוצה בת [math]\displaystyle{ n }[/math] איברים. יש [math]\displaystyle{ D(n,k):=\left(\!\!\!\binom nk\!\!\!\right):=\binom{n-1+k}k }[/math] צירופים עם חזרות.

מספר הצירופים עם חזרות של [math]\displaystyle{ k }[/math] מתוך [math]\displaystyle{ n }[/math] שווה למספר הדרכים לבחור [math]\displaystyle{ k }[/math] עצמים מתוך [math]\displaystyle{ n }[/math] סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־[math]\displaystyle{ \sum_{i=1}^n x_i=k }[/math].

הווקטור האופייני של קבוצה [math]\displaystyle{ A\subseteq [n] }[/math] מוגדר ע״י [math]\displaystyle{ \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]\displaystyle{ (a_i)_{i=1}^n }[/math] כך שקיים [math]\displaystyle{ k }[/math] עבורו [math]\displaystyle{ (a_i)_{i=1}^k }[/math] עולה במובן הרחב ו־[math]\displaystyle{ (a_i)_{i=k}^n }[/math] יורדת במובן הרחב.

[math]\displaystyle{ \Big(\tbinom ni\Big)_{i=0}^n }[/math] היא סדרה אונימוצלית כאשר אם [math]\displaystyle{ n }[/math] זוגי אז [math]\displaystyle{ k=n/2 }[/math] ואחרת [math]\displaystyle{ k=\lfloor n/2\rfloor,\lceil n/2\rceil }[/math] (כי [math]\displaystyle{ \binom n{\lfloor n/2\rfloor}=\binom n{\lceil n/2\rceil} }[/math]).

הפרת סדר בתמורה [math]\displaystyle{ \pi }[/math] היא זוג [math]\displaystyle{ i\lt j }[/math] כך ש־[math]\displaystyle{ \pi(j)\lt \pi(i) }[/math]. מספר הפרות הסדר מסומן [math]\displaystyle{ \mbox{inv}(\pi) }[/math] וסימן התמורה מוגדר כ־[math]\displaystyle{ \sgn(\pi):=(-1)^{\mbox{inv}(\pi)} }[/math]. התמרה [math]\displaystyle{ \pi }[/math] תקרא זוגית אם [math]\displaystyle{ \sgn(\pi)=1 }[/math] ואי־זוגית אחרת. יש [math]\displaystyle{ n!/2 }[/math] התמרות מכל סוג שסדרן [math]\displaystyle{ n }[/math].
מורד: עבור [math]\displaystyle{ \pi\in S_n }[/math] נקרא ל־[math]\displaystyle{ i }[/math] מורָד (descent) אם [math]\displaystyle{ \pi(i)\gt \pi(i+1) }[/math]. קבוצת המורדות תסומן [math]\displaystyle{ \mbox{Des}(\pi) }[/math].

[math]\displaystyle{ \left|\Big\{\pi\in S_n:\ \mbox{Des}(\pi)\subseteq\{k\}\Big\}\right|=\binom nk }[/math].

אי־סדר מלא הוא תמורה [math]\displaystyle{ \pi\in S_n }[/math] כך ש־[math]\displaystyle{ \forall i:\ \pi(i)\ne i }[/math]. קבוצת האי־סדרים המלאים ב־[math]\displaystyle{ S_n }[/math] מסומנת [math]\displaystyle{ D_n }[/math] ומקיימת [math]\displaystyle{ |D_n|=n!\sum_{i=0}^n\frac{(-1)^i}{i!} }[/math].
אם [math]\displaystyle{ 0\lt k\lt p }[/math] אז [math]\displaystyle{ p\mid\binom pk }[/math].
יהי פולינום [math]\displaystyle{ f(x)=\sum_{k=0}^n a_kx^k }[/math]. נסמן [math]\displaystyle{ (f\mod m)(x):=\sum_{k=0}^n(a_k\mod m)x^k }[/math].
[math]\displaystyle{ (1+x)^p\mod p=1+x^p }[/math].
משפט פרמה הקטן: [math]\displaystyle{ n^p\equiv n\pmod p }[/math].
פיתוח של מספר לפי ראשוני: נניח [math]\displaystyle{ p^d\le n }[/math] ו־[math]\displaystyle{ n\lt p^{d+1} }[/math]. אזי קיימים [math]\displaystyle{ a_0,\dots,a_d }[/math] שלמים כך ש־[math]\displaystyle{ \forall i:\ 0\le a_i\lt p }[/math] ו־[math]\displaystyle{ n=\sum_{i=0}^d a_ip^i }[/math]. סכום זה נקרא "הפיתוח של [math]\displaystyle{ n }[/math] לפי [math]\displaystyle{ p }[/math]".
אם [math]\displaystyle{ n=2^d-1 }[/math] אז [math]\displaystyle{ \forall 0\le k\le n:\ 2\nmid\binom nk }[/math]. לפיכך, [math]\displaystyle{ n=\sum_{i=0}^{d-1}2^i }[/math].
משפט לוקאס: נניח ש־[math]\displaystyle{ n=\sum_{i=0}^d a_i p^i }[/math] ו־[math]\displaystyle{ k=\sum_{i=0}^d b_i p^i }[/math] פיתוחים לפי [math]\displaystyle{ p }[/math]. אזי [math]\displaystyle{ \binom nk\equiv\prod_{i=0}^d\binom{a_i}{b_i}\pmod p }[/math].
[math]\displaystyle{ p\mid\binom nk }[/math] אם״ם בפיתוחים [math]\displaystyle{ n=\sum_{i=0}^d a_i p^i\ \and\ k=\sum_{i=0}^d b_i p^i }[/math] יש [math]\displaystyle{ i_0 }[/math] עבורו [math]\displaystyle{ a_{i_0}\lt b_{i_0} }[/math].
פירוק/קומפוזיציה של [math]\displaystyle{ n }[/math] הוא הצגה של [math]\displaystyle{ n }[/math] כסכום של טבעיים.

יש [math]\displaystyle{ 2^{n-1} }[/math] פירוקים של [math]\displaystyle{ n }[/math] (כאשר יש חשיבות לסדר ([math]\displaystyle{ 2+1 }[/math] שונה מ־[math]\displaystyle{ 1+2 }[/math]) וחזרות מותרות ([math]\displaystyle{ 1+1+1 }[/math] ייספר כפירוק של 3)).

מקדם מולטינומי: מספר המילים מאורך [math]\displaystyle{ n }[/math] שבהן המספר [math]\displaystyle{ i }[/math] מופיע [math]\displaystyle{ n_i }[/math] פעמים ([math]\displaystyle{ \sum_i n_i=n }[/math]) הוא [math]\displaystyle{ \binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right. }[/math].
סימונים: [math]\displaystyle{ [n]_q:=\sum_{i=0}^{n-1}q^i }[/math]. כמו כן, [math]\displaystyle{ [n]_q!:=\prod_{i=1}^n [i]_q,\ [0]_q!=1 }[/math] ו־[math]\displaystyle{ \forall 0\le k\le n:\ \begin{bmatrix}n\\k\end{bmatrix}_q:=\frac{[n]_q!}{[k]_q![n-k]_q!} }[/math]. ניתן להראות ש־[math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_q }[/math] שלם.

[math]\displaystyle{ [n]_1=n }[/math] ו־[math]\displaystyle{ \forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1} }[/math].
אם [math]\displaystyle{ q }[/math] זוגי אז [math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_q }[/math] אי־זוגי.
מספר התתי־מרחבים ממימד [math]\displaystyle{ k }[/math] של מרחב וקטורי [math]\displaystyle{ \mathbb F^n }[/math] (כאשר ל־[math]\displaystyle{ \mathbb F }[/math] יש [math]\displaystyle{ q }[/math] איברים) הוא [math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_q }[/math].

אם [math]\displaystyle{ 0\le k\le n }[/math] אז [math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_q\in\mathbb N_0[q] }[/math], כלומר זה פולינום במשתנה [math]\displaystyle{ q }[/math] שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו [math]\displaystyle{ k(n-k) }[/math] והוא סימטרי (כלומר המקדם של [math]\displaystyle{ q^i }[/math] שווה למקדם של [math]\displaystyle{ q^{k(n-k)-i} }[/math] לכל [math]\displaystyle{ 0\le i\le k(n-k) }[/math]).
הילוך שריג הוא סדרת צעדים בין נקודות ב־[math]\displaystyle{ \mathbb Z^2 }[/math] שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.

יש [math]\displaystyle{ \binom{m+n}n }[/math] הילוכי שריג מ־[math]\displaystyle{ (0,0) }[/math] ל־[math]\displaystyle{ (m,n) }[/math].
נסמן [math]\displaystyle{ C_t(m,n) }[/math] כמספר הילוכי השריג מ־[math]\displaystyle{ (0,0) }[/math] ל־[math]\displaystyle{ (m,n) }[/math] שהשטח המוגבל על־ידם, ציר ה־x והישר [math]\displaystyle{ x=m }[/math] הוא [math]\displaystyle{ t }[/math]. בנוסף, נגדיר [math]\displaystyle{ P_{m,n}(q)=\sum_{t=0}^{mn} C_t(m,n)q^t }[/math]. אזי [math]\displaystyle{ P_{m,n}(q)=\begin{bmatrix}m+n\\n\end{bmatrix}_q }[/math].

נסמן [math]\displaystyle{ I_n(q):=\sum_{\pi\in S_n}q^{\mbox{inv}(\pi)} }[/math]. אזי [math]\displaystyle{ I_n(q)=[n]_q! }[/math].
יהי [math]\displaystyle{ \mathbf v=(v_i)_{i=1}^n\in\mathbb Z_2^n }[/math] וקטור שרכיביו אפסים ואחדות. אם [math]\displaystyle{ i\lt j }[/math] ו־[math]\displaystyle{ v_i\gt v_j }[/math] נכנה זאת הפרת סדר. אם נסמן [math]\displaystyle{ 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]\displaystyle{ I_{n,k}(q)=\begin{bmatrix}n\\k\end{bmatrix}_q }[/math].
חלוקה של [math]\displaystyle{ n }[/math] היא וקטור [math]\displaystyle{ \boldsymbol\lambda=(\lambda_1,\dots,\lambda_k) }[/math] שסכום רכיביו הוא [math]\displaystyle{ n }[/math] (כלומר [math]\displaystyle{ \sum_{i=1}^k\lambda_i=n }[/math]) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן [math]\displaystyle{ p(n) }[/math].

מספר החלוקות של [math]\displaystyle{ n }[/math] עם לכל היותר [math]\displaystyle{ k }[/math] רכיבים הוא המקדם של [math]\displaystyle{ q^n }[/math] בפולינום [math]\displaystyle{ \begin{bmatrix}n+k\\k\end{bmatrix}_q }[/math], כלומר [math]\displaystyle{ C_n(n,k) }[/math].

דיאגרמת יאנג של חלוקה [math]\displaystyle{ (\lambda_1,\dots,\lambda_k) }[/math] היא דיאגרמת משבצות כך שבשורה ה־[math]\displaystyle{ i }[/math] יש [math]\displaystyle{ \lambda_i }[/math] משבצות המיושרות לשמאל.
טבלת יאנג היא התאמה חח״ע ממשבצות של דיאגרמת יאנג נתונה (שנוצרת מחלוקה של [math]\displaystyle{ n }[/math]) על [math]\displaystyle{ [n] }[/math] כך שהמספרים עולים לאורך השורות העמודות.

[math]\displaystyle{ f(\boldsymbol\lambda) }[/math] היא מספר טבלאות יאנג שקיימות לדיאגרמת יאנג הנוצרת מהחלוקה [math]\displaystyle{ \boldsymbol\lambda }[/math].

[math]\displaystyle{ 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]\displaystyle{ \boldsymbol\lambda }[/math] ונרצה לחשב את [math]\displaystyle{ f(\boldsymbol\lambda) }[/math]. לכל משבצת בדיאגרמת יאנג נתאים "אורך וו" (hook length) כמספר המשבצות באותה שורה או עמודה שאחרי המשבצת הנתונה ועוד 1. נסמן [math]\displaystyle{ \Pi }[/math] כמכפלת אורכי הווים של כל המשבצות. אזי [math]\displaystyle{ f(\boldsymbol\lambda)=\frac{n!}\Pi }[/math].

הילוכי דיק הם הילוכי שריג מ־[math]\displaystyle{ (0,0) }[/math] ל־[math]\displaystyle{ (n,n) }[/math] שנמצאים על ומעל הישר [math]\displaystyle{ x=y }[/math].
מספר קטלן הוא מספר הילוכי דיק ל־[math]\displaystyle{ (n,n) }[/math], מסומן [math]\displaystyle{ C_n }[/math] ושווה ל־[math]\displaystyle{ \frac1{n+1}\binom{2n}n }[/math].

נניח ש־[math]\displaystyle{ 0\lt a\lt b }[/math]. יש [math]\displaystyle{ \frac{b-a}{b+a}\binom{a+b}a }[/math] הילוכי דיק ל־[math]\displaystyle{ (a,b) }[/math] שאינם עוברים על הישר [math]\displaystyle{ x=y }[/math] למעט בנקודה [math]\displaystyle{ (0,0) }[/math].
מילת דיק מאורך [math]\displaystyle{ 2n }[/math] היא סדרה [math]\displaystyle{ (a_i)_{i=1}^{2n} }[/math] כך ש־[math]\displaystyle{ \forall i:\ a_i\in\{\pm1\} }[/math], [math]\displaystyle{ \forall k:\ \sum_{i=1}^k a_i\ge0 }[/math] ו־[math]\displaystyle{ \sum_{i=1}^{2n}a_i=0 }[/math]. יש [math]\displaystyle{ C_n }[/math] מילות דיק מאורך [math]\displaystyle{ 2n }[/math].
עץ בינארי שלם/מלא הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש [math]\displaystyle{ C_n }[/math] עצים בינארים מלאים עם [math]\displaystyle{ n+1 }[/math] עלים.
בהינתן מכפלה לא אסוציאטיבית [math]\displaystyle{ x_1\cdot x_2\cdot\dots\cdot x_{n+1} }[/math] יש [math]\displaystyle{ C_n }[/math] דרכים להוסיף סוגריים.
שילוש של מצולע משוכלל בעל [math]\displaystyle{ n }[/math] קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו [math]\displaystyle{ n-3 }[/math] אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש [math]\displaystyle{ C_n }[/math] דרכים לשלש מצולע משוכלל בעל [math]\displaystyle{ n+2 }[/math] צלעות.

מספר בל הוא מספר חלוקות הקבוצה [math]\displaystyle{ [n] }[/math] ומסומן [math]\displaystyle{ B_n }[/math].
מספר סטירלינג הלא מסומן מסוג I הוא מספר התמורות על [math]\displaystyle{ [n] }[/math] עם [math]\displaystyle{ k }[/math] מחזורים ומסומן [math]\displaystyle{ C(n,k) }[/math].

[math]\displaystyle{ n!=\sum_{k=1}^n C(n,k) }[/math].
[math]\displaystyle{ C(n,n)=1\ \and\ C(n,1)=(n-1)! }[/math].

מספר סטירלינג מסוג I הוא [math]\displaystyle{ s(n,k):=(-1)^{n-k}C(n,k) }[/math].

יהי [math]\displaystyle{ N\in\mathbb N }[/math]. נסמן [math]\displaystyle{ s_N\in\mathbb R^{N\times N} }[/math] בתור המטריצה שהרכיב בשורה ה־[math]\displaystyle{ n }[/math] ובעמודה ה־[math]\displaystyle{ k }[/math] שלה הוא [math]\displaystyle{ s(n,k) }[/math].
[math]\displaystyle{ \sum_{k=1}^n s(n,k)x^k=(x)_n }[/math].

מספר סטירלינג מסוג II הוא מספר חלוקות הקבוצה [math]\displaystyle{ [n] }[/math] ל־[math]\displaystyle{ k }[/math] תתי־קבוצות לא ריקות ומסומן [math]\displaystyle{ S(n,k) }[/math].

[math]\displaystyle{ B_n=\sum_{k=1}^n S(n,k) }[/math].
יהי [math]\displaystyle{ N\in\mathbb N }[/math]. נסמן [math]\displaystyle{ S_N\in\mathbb R^{N\times N} }[/math] בתור המטריצה שהרכיב בשורה ה־[math]\displaystyle{ n }[/math] ובעמודה ה־[math]\displaystyle{ k }[/math] שלה הוא [math]\displaystyle{ S(n,k) }[/math].
[math]\displaystyle{ \sum_{k=1}^n S(n,k)(x)_k=x^n }[/math].

[math]\displaystyle{ S_N=s_N^{-1} }[/math].

פונקציות יוצרות[עריכה]

טור חזקות פורמלי במשתנה [math]\displaystyle{ x }[/math] מכל [math]\displaystyle{ \mathbb F }[/math] (בד״כ [math]\displaystyle{ \mathbb Q,\mathbb R,\mathbb C }[/math]) הוא ביטוי מהצורה [math]\displaystyle{ \sum_{i=0}^\infty a_ix^i }[/math] כאשר [math]\displaystyle{ \forall i:\ a_i\in\mathbb F }[/math]. הטור לא חייב להתכנס. אוסף טורי החזקות הפורמליים ב־[math]\displaystyle{ x }[/math] מעל [math]\displaystyle{ \mathbb F }[/math] מסומן [math]\displaystyle{ \mathbb F[[x]] }[/math].

אם [math]\displaystyle{ \exists n_0:\ \forall i\gt n_0:\ a_i=0 }[/math] אז הטור הוא פולינום. אוסף הפולינומים ב־[math]\displaystyle{ x }[/math] מעל [math]\displaystyle{ \mathbb F }[/math] מסומן [math]\displaystyle{ \mathbb F[x] }[/math].

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

נוסחאות נסיגה[עריכה]

נוסחת נסיגה מסדר [math]\displaystyle{ k }[/math] היא נוסחה מהצורה [math]\displaystyle{ \forall n\ge k:\ a_n=f(a_{n-1},a_{n-2},\dots,a_{n-k}) }[/math].

איברי סדרה המקיימת נוסחת נסיגה כזו נקבעים ע״י [math]\displaystyle{ k }[/math] האיברים הראשונים, והם נקראים תנאי ההתחלה.
נוסחת נסיגה לינארית מסדר [math]\displaystyle{ k }[/math] היא נוסחה מהצורה [math]\displaystyle{ \forall n\ge k:\ a_n=f(n)+\sum_{i=1}^k c_i(n)a_{n-i} }[/math]. אם [math]\displaystyle{ c_i }[/math] פונקציות קבועות אז נאמר שהנוסחה עם מקדמים קבועים. אם [math]\displaystyle{ f(n)\equiv0 }[/math] אז נאמר שהיא הומוגנית.

קבוצת הסדרות הפותרות נוסחת נסיגה לינארית הומוגנית מסדר [math]\displaystyle{ k }[/math] היא מרחב וקטורי ממימד [math]\displaystyle{ k }[/math].

נרצה לחשב את אברי [math]\displaystyle{ (a_i)_{i=0}^\infty }[/math] בהינתן תנאי ההתחלה [math]\displaystyle{ (a_i)_{i=0}^{k-1} }[/math] ונוסחת נסיגה [math]\displaystyle{ \forall i\ge k:\ a_i=g(a_{i-1},\dots,a_{i-k}) }[/math]. נעזר בפונקציה היוצרת [math]\displaystyle{ f(x)=\sum_{i=0}^\infty a_i x^i }[/math] ואם קיימת פונקציה [math]\displaystyle{ G }[/math] עבורה
[math]\displaystyle{ \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]\displaystyle{ f(x) }[/math] ונקבל נוסחה מפורשת למקדמים [math]\displaystyle{ a_i }[/math] של [math]\displaystyle{ x^i }[/math].
תהי נוסחת נסיגה לינארית הומוגנית עם מקדמים קבועים [math]\displaystyle{ a_n=\sum_{i=1}^k c_i a_{n-i} }[/math] מסדר [math]\displaystyle{ k }[/math]. נניח שיש [math]\displaystyle{ \alpha\in\mathbb C }[/math] עבורו [math]\displaystyle{ \forall n:\ a_n=\alpha^n }[/math] (לא תמיד זה נכון). אזי [math]\displaystyle{ \alpha=0 }[/math] פתרון. [math]\displaystyle{ x^k-\sum_{i=1}^k c_i x^{k-i} }[/math] נקרא "הפולינום האופייני של נוסחת הנסיגה" ואם [math]\displaystyle{ \alpha\ne0 }[/math] אז הוא שווה ל־0 בנקודה [math]\displaystyle{ \alpha }[/math]. יש לו [math]\displaystyle{ k }[/math] שורשים אם כל שורשיו מריבוי 1 ואם נניח שהם [math]\displaystyle{ \alpha_1,\dots,\alpha_k }[/math] אז [math]\displaystyle{ \forall n,i:\ a_n=\alpha_i^n }[/math]. המרחב הווקטורי של הפתרונות הוא אם כן [math]\displaystyle{ \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]\displaystyle{ r_i }[/math]־ים.

נוסחאות[עריכה]

נוסחת הנסיגה של פסקל: [math]\displaystyle{ \binom nk=\binom{n-1}k+\binom{n-1}{k-1} }[/math]
[math]\displaystyle{ \binom nk=\sum_{i=k}^n\binom{i-1}{k-1} }[/math]
זהות הקפטן: [math]\displaystyle{ k\binom nk=n\binom{n-1}{k-1} }[/math]
הבינום של ניוטון: [math]\displaystyle{ (1+x)^\alpha=\sum_{k=0}^n\binom\alpha k x^k }[/math]
[math]\displaystyle{ \forall 0\le m\le k\le n:\ \binom nk\binom km=\binom nm\binom{n-m}{k-m} }[/math]
[math]\displaystyle{ \sum_{k=0}^n\binom nk=2^n }[/math]
[math]\displaystyle{ \sum_{2\mid k}\binom nk=\sum_{2\nmid k}\binom nk=2^{n-1} }[/math]
[math]\displaystyle{ \sum_{k=0}^n\binom nk^2=\binom{2n}n }[/math]
[math]\displaystyle{ \sum_{k=0}^n k\binom nk=2^{n-1}n }[/math]
[math]\displaystyle{ \forall 8\mid n:\ \sum_{4\mid k}\binom nk=2^{n-2}+2^{n/2-1} }[/math]
[math]\displaystyle{ \sum_{\sum_{i=1}^k n_i=n}\binom n{n_1,\dots,n_k}=k^n }[/math]
[math]\displaystyle{ \binom n{n_1,\dots,n_k}=\prod_{i=1}^k\binom {n-\sum_{j=1}^{i-1} n_j}{n_i} }[/math]
נוסחת המולטינום: [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \forall q\gt 1:\ \begin{bmatrix}n\\k\end{bmatrix}_q=\prod_{i=1}^k\frac{q^{n-k+i}-1}{q^i-1} }[/math]
[math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_q=\begin{bmatrix}n\\n-k\end{bmatrix}_q }[/math]
[math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix}_1=\binom nk }[/math]
נוסחת q־פסקל: [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \forall n\gt 1:\ C_n=\sum_{i=1}^{n-1}C_i C_{n-i} }[/math] ו־[math]\displaystyle{ C_0=C_1=1 }[/math]
נוסחת נסיגה למספרי בל: [math]\displaystyle{ \forall n\gt 0:\ B_n=\sum_{k=1}^n\binom{n-1}{k-1}B_{n-k} }[/math] ו־[math]\displaystyle{ B_0=1 }[/math]
נוסחת נסיגה למספרי סטירלינג לא מסומנים מסוג I: [math]\displaystyle{ \forall n\in\mathbb N,k\in[n]:\ C(n,k)=C(n-1,k-1)+(n-1)C(n-1,k) }[/math] ו־[math]\displaystyle{ C(0,0)=1\ \and\ \forall n\lt k:\ C(n,k)=0\ \and\ \forall n\gt 0:\ C(n,0)=0 }[/math]
נוסחת נסיגה למספרי סטירלינג מסוג I: [math]\displaystyle{ \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]\displaystyle{ \forall n\in\mathbb N,k\in[n]:\ S(n,k)=S(n-1,k-1)+k S(n-1,k) }[/math] ו־[math]\displaystyle{ S(0,0)=1\ \and\ \forall n\lt k:\ s(n,k)=0\ \and\ \forall n\gt 0:\ S(n,0)=0 }[/math]
[math]\displaystyle{ \binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n }[/math]
[math]\displaystyle{ \forall n\gt 0:\ \binom{1/2}n=\frac{C_{n-1}}2\left(\frac{-1}4\right)^{n-1} }[/math]
[math]\displaystyle{ \sum_{n=0}^\infty p(n)x^n=\prod_{n=1}^\infty\frac1{1-x^n} }[/math]