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

מתוך Math-Wiki
גרסה מ־13:06, 9 באוקטובר 2013 מאת אור שחף (שיחה | תרומות) (נוסחאות נסיגה)

(הבדל) → הגרסה הקודמת | הגרסה האחרונה (הבדל) | הגרסה הבאה ← (הבדל)
קפיצה אל: ניווט, חיפוש

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

  • נסמן [n]:=\{1,2,\dots,n\}=[1,n]\cap\mathbb N. S_n היא קבוצת כל התמורות על [n].
  • חלוקת קבוצות של A ל־n היא בחירה של תתי־קבוצות A_1,\dots,A_n\subseteq A זרות עבורן \biguplus_{k=1}^n A_k=A.
  • סדרת פיבונצ׳י תסומן (F_n)_{n=0}^\infty והיא מקיימת F_n=\frac{5-\sqrt5}{10}\left(\frac{1-\sqrt5}2\right)^n+\frac2{5-\sqrt5}\left(\frac{1+\sqrt5}2\right)^n.
  • ריצוף דומינו של A\subseteq\mathbb Z^2 הוא כיסוי של A על ידי קטעים זרים מאורך 1 שקצותיהם נקודות ב־A.
  • ללוח בגודל m\times n קיים ריצוף דומינו אם״ם mn זוגי.
  • ללוח בגודל 2\times n קיימים F_n ריצופי דומינו.
  • עקרון שובך יונים: בחלוקה של קבוצה סופית A ל־n יש לפחות תת־קבוצה אחת שמספר איבריה הוא לכל הפחות |A|/n.
  • סימונים: (\alpha)_k:=\prod_{i=0}^{k-1}(\alpha-i) ו־(n)_k=\begin{cases}\frac{n!}{(n-k)!},&k\le n\\0,&\text{else}\end{cases}. בנוסף, \binom nk:=\begin{cases}\frac{n!}{k!(n-k)!},&0\le k\le n\\0,&\text{else}\end{cases} ו־\binom\alpha k:=\frac{(\alpha)_k}{k!}.
  • חליפה: נניח 0\le k\le n. חליפה של k איברים מתוך n היא k־יה סדורה של איברים שונים מקבוצה בת n איברים (כלומר, חליפה היא בחירה ללא חזרות ועם חשיבות לסדר). מספר החליפות הוא P(n,k):=(n)_k.
  • תמורה היא חליפה של n מתוך n, ומספר התמורות הוא P(n):=(n)_n=n!.
  • חליפה עם חזרות היא k־יה סדורה של k איברים (לא דווקא שונים) מתוך n. יש n^k חליפות עם חזרות.
  • צירוף: נניח 0\le k\le n. צירוף של k איברים מתוך n הוא תת־קבוצה של קבוצה בת n איברים (כלומר, צירוף הוא בחירה ללא חזרות ובלי חשיבות לסדר). מספר הצירופים הוא C(n,k):=\binom nk.
  • צירוף עם חזרות: הוא רב־קבוצה מסדר k של איברים מתוך קבוצה בת n איברים. יש D(n,k):=\left(\!\!\!\binom nk\!\!\!\right):=\binom{n-1+k}k צירופים עם חזרות.
  • מספר הצירופים עם חזרות של k מתוך n שווה למספר הדרכים לבחור k עצמים מתוך n סוגים, ששווה למספר הפתרונות השלמים ואי־שליליים ל־\sum_{i=1}^n x_i=k.
  • הווקטור האופייני של קבוצה A\subseteq [n] מוגדר ע״י \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.
  • סדרה אונימוצלית היא סדרה (a_i)_{i=1}^n כך שקיים k עבורו (a_i)_{i=1}^k עולה במובן הרחב ו־(a_i)_{i=k}^n יורדת במובן הרחב.
  • \Big(\tbinom ni\Big)_{i=0}^n היא סדרה אונימוצלית כאשר אם n זוגי אז k=n/2 ואחרת k=\lfloor n/2\rfloor,\lceil n/2\rceil (כי \binom n{\lfloor n/2\rfloor}=\binom n{\lceil n/2\rceil}).
  • הפרת סדר בתמורה \pi היא זוג i<j כך ש־\pi(j)<\pi(i). מספר הפרות הסדר מסומן \mbox{inv}(\pi) וסימן התמורה מוגדר כ־\sgn(\pi):=(-1)^{\mbox{inv}(\pi)}. התמרה \pi תקרא זוגית אם \sgn(\pi)=1 ואי־זוגית אחרת. יש n!/2 התמרות מכל סוג שסדרן n.
  • מורד: עבור \pi\in S_n נקרא ל־i מורָד (descent) אם \pi(i)>\pi(i+1). קבוצת המורדות תסומן \mbox{Des}(\pi).
  • \left|\Big\{\pi\in S_n:\ \mbox{Des}(\pi)\subseteq\{k\}\Big\}\right|=\binom nk.
  • אי־סדר מלא הוא תמורה \pi\in S_n כך ש־\forall i:\ \pi(i)\ne i. קבוצת האי־סדרים המלאים ב־S_n מסומנת D_n ומקיימת |D_n|=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.
  • אם 0<k<p אז p\mid\binom pk.
  • יהי פולינום f(x)=\sum_{k=0}^n a_kx^k. נסמן (f\mod m)(x):=\sum_{k=0}^n(a_k\mod m)x^k.
  • (1+x)^p\mod p=1+x^p.
  • משפט פרמה הקטן: n^p\equiv n\pmod p.
  • פיתוח של מספר לפי ראשוני: נניח p^d\le n ו־n<p^{d+1}. אזי קיימים a_0,\dots,a_d שלמים כך ש־\forall i:\ 0\le a_i<p ו־n=\sum_{i=0}^d a_ip^i. סכום זה נקרא "הפיתוח של n לפי p".
  • אם n=2^d-1 אז \forall 0\le k\le n:\ 2\nmid\binom nk. לפיכך, n=\sum_{i=0}^{d-1}2^i.
  • משפט לוקאס: נניח ש־n=\sum_{i=0}^d a_i p^i ו־k=\sum_{i=0}^d b_i p^i פיתוחים לפי p. אזי \binom nk\equiv\prod_{i=0}^d\binom{a_i}{b_i}\pmod p.
  • p\mid\binom nk אם״ם בפיתוחים n=\sum_{i=0}^d a_i p^i\ \and\ k=\sum_{i=0}^d b_i p^i יש i_0 עבורו a_{i_0}<b_{i_0}.
  • פירוק/קומפוזיציה של n הוא הצגה של n כסכום של טבעיים.
  • יש 2^{n-1} פירוקים של n (כאשר יש חשיבות לסדר (2+1 שונה מ־1+2) וחזרות מותרות (1+1+1 ייספר כפירוק של 3)).
  • מקדם מולטינומי: מספר המילים מאורך n שבהן המספר i מופיע n_i פעמים (\sum_i n_i=n) הוא \binom n{n_1,n_2,\dots}=n!\left/\prod_i n_i!\right..
  • סימונים: [n]_q:=\sum_{i=0}^{n-1}q^i. כמו כן, [n]_q!:=\prod_{i=1}^n [i]_q,\ [0]_q!=1 ו־\forall 0\le k\le n:\ \begin{bmatrix}n\\k\end{bmatrix}_q:=\frac{[n]_q!}{[k]_q![n-k]_q!}. ניתן להראות ש־\begin{bmatrix}n\\k\end{bmatrix}_q שלם.
  • [n]_1=n ו־\forall q\ne 1:\ [n]_q=\frac{q^n-1}{q-1}.
  • אם q זוגי אז \begin{bmatrix}n\\k\end{bmatrix}_q אי־זוגי.
  • מספר התתי־מרחבים ממימד k של מרחב וקטורי \mathbb F^n (כאשר ל־\mathbb F יש q איברים) הוא \begin{bmatrix}n\\k\end{bmatrix}_q.
  • אם 0\le k\le n אז \begin{bmatrix}n\\k\end{bmatrix}_q\in\mathbb N_0[q], כלומר זה פולינום במשתנה q שמקדמיו שלמים ואי־שליליים. למעשה, הוא גם מתוקן, דרגתו k(n-k) והוא סימטרי (כלומר המקדם של q^i שווה למקדם של q^{k(n-k)-i} לכל 0\le i\le k(n-k)).
  • הילוך שריג הוא סדרת צעדים בין נקודות ב־\mathbb Z^2 שכל אחד מהם הוא הוספת 1 לאחת מהקואורדינטות של הנקודה בה נמצאים.
  • יש \binom{m+n}n הילוכי שריג מ־(0,0) ל־(m,n).
  • נסמן C_t(m,n) כמספר הילוכי השריג מ־(0,0) ל־(m,n) שהשטח המוגבל על־ידם, ציר ה־x והישר x=m הוא t. בנוסף, נגדיר P_{m,n}(q)=\sum_{t=0}^{mn} C_t(m,n)q^t. אזי P_{m,n}(q)=\begin{bmatrix}m+n\\n\end{bmatrix}_q.
  • נסמן I_n(q):=\sum_{\pi\in S_n}q^{\mbox{inv}(\pi)}. אזי I_n(q)=[n]_q!.
  • יהי \mathbf v=(v_i)_{i=1}^n\in\mathbb Z_2^n וקטור שרכיביו אפסים ואחדות. אם i<j ו־v_i>v_j נכנה זאת הפרת סדר. אם נסמן I_{n,k}(q)=\sum_{\mathbf v\in\mathbb Z_2^n\ \and\ |\{i:\ v_i=1\}|=k}q^{\mbox{inv}(\mathbf v)} אז I_{n,k}(q)=\begin{bmatrix}n\\k\end{bmatrix}_q.
  • חלוקה של n היא וקטור \boldsymbol\lambda=(\lambda_1,\dots,\lambda_k) שסכום רכיביו הוא n (כלומר \sum_{i=1}^k\lambda_i=n) והם מסודרים בסדר יורד במובן הרחב. מספר החלוקות מסומן p(n).
  • מספר החלוקות של n עם לכל היותר k רכיבים הוא המקדם של q^n בפולינום \begin{bmatrix}n+k\\k\end{bmatrix}_q, כלומר C_n(n,k).
  • דיאגרמת יאנג של חלוקה (\lambda_1,\dots,\lambda_k) היא דיאגרמת משבצות כך שבשורה ה־i יש \lambda_i משבצות המיושרות לשמאל.
  • טבלת יאנג היא התאמה חח״ע ממשבצות של דיאגרמת יאנג נתונה (שנוצרת מחלוקה של n) על [n] כך שהמספרים עולים לאורך השורות העמודות.
  • f(\boldsymbol\lambda) היא מספר טבלאות יאנג שקיימות לדיאגרמת יאנג הנוצרת מהחלוקה \boldsymbol\lambda.
  • 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.
  • נוסחת הווים: תהי \boldsymbol\lambda ונרצה לחשב את f(\boldsymbol\lambda). לכל משבצת בדיאגרמת יאנג נתאים "אורך וו" (hook length) כמספר המשבצות באותה שורה או עמודה שאחרי המשבצת הנתונה ועוד 1. נסמן \Pi כמכפלת אורכי הווים של כל המשבצות. אזי f(\boldsymbol\lambda)=\frac{n!}\Pi.
  • הילוכי דיק הם הילוכי שריג מ־(0,0) ל־(n,n) שנמצאים על ומעל הישר x=y.
  • מספר קטלן הוא מספר הילוכי דיק ל־(n,n), מסומן C_n ושווה ל־\frac1{n+1}\binom{2n}n.
  • נניח ש־0<a<b. יש \frac{b-a}{b+a}\binom{a+b}a הילוכי דיק ל־(a,b) שאינם עוברים על הישר x=y למעט בנקודה (0,0).
  • מילת דיק מאורך 2n היא סדרה (a_i)_{i=1}^{2n} כך ש־\forall i:\ a_i\in\{\pm1\}, \forall k:\ \sum_{i=1}^k a_i\ge0 ו־\sum_{i=1}^{2n}a_i=0. יש C_n מילות דיק מאורך 2n.
  • עץ בינארי שלם/מלא הוא עץ כך שלכל אב יש בדיוק 2 בנים, כלומר לכל קודקוד שאינו עלה יש דרגה 3 למעט קודקוד אחד, שנקרא שורש. אם מבדילים בין הבן הימני לבן השמאלי אז יש C_n עצים בינארים מלאים עם n+1 עלים.
  • בהינתן מכפלה לא אסוציאטיבית x_1\cdot x_2\cdot\dots\cdot x_{n+1} יש C_n דרכים להוסיף סוגריים.
  • שילוש של מצולע משוכלל בעל n קודקודים הוא מבנה גיאומטרי הנוצר מהמצולע כשמעבירים בו n-3 אלכסונים שאינם חותכים זה את זה פרט לבקודקודי המצולע. יש C_n דרכים לשלש מצולע משוכלל בעל n+2 צלעות.
  • מספר בל הוא מספר חלוקות הקבוצה [n] ומסומן B_n.
  • מספר סטירלינג הלא מסומן מסוג I הוא מספר התמורות על [n] עם k מחזורים ומסומן C(n,k).
  • n!=\sum_{k=1}^n C(n,k).
  • C(n,n)=1\ \and\ C(n,1)=(n-1)!.
  • מספר סטירלינג מסוג I הוא s(n,k):=(-1)^{n-k}C(n,k).
  • יהי N\in\mathbb N. נסמן s_N\in\mathbb R^{N\times N} בתור המטריצה שהרכיב בשורה ה־n ובעמודה ה־k שלה הוא s(n,k).
  • \sum_{k=1}^n s(n,k)x^k=(x)_n.
  • מספר סטירלינג מסוג II הוא מספר חלוקות הקבוצה [n] ל־k תתי־קבוצות לא ריקות ומסומן S(n,k).
  • B_n=\sum_{k=1}^n S(n,k).
  • יהי N\in\mathbb N. נסמן S_N\in\mathbb R^{N\times N} בתור המטריצה שהרכיב בשורה ה־n ובעמודה ה־k שלה הוא S(n,k).
  • \sum_{k=1}^n S(n,k)(x)_k=x^n.
  • S_N=s_N^{-1}.

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

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

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

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

נוסחאות

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