הבדלים בין גרסאות בדף "תקציר מבוא לקומבינטוריקה, סמסטר א תשע״ג"

גרסה מ־22:17, 2 בפברואר 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$ .
ריצוף דומינו של $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 n:=\frac{(\alpha)_n}{n!}$ .
חליפה: נניח $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$ .

אם $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}^{q-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$ משבצות המיושרות לשמאל.
הילוכי דיק הם הילוכי שריג מ־ $(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$ .
מספר סטיכלינג מסוג 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$ .

מספר סטיכלינג הלא מסומן מסוג 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$ .

$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}^k t_i=n$ כאשר $\forall i:\ t_i\in A_i\subseteq\mathbb N_0$ . נתאים לכל משתנה פונקציה יוצרת $f_i(x)=\sum_{t\in A_i} x^t$ ולכן מספר הפתרונות הדרוש הוא המקדם של $x^n$ ב־ $\prod_{i=1}^k 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)$ .

נוסחאות

נוסחת הנסיגה של פסקל: $\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$
אם $1\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$
אם $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}$
$\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:\ \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k}$ ו־ $B_0=1$
נוסחת נסיגה למספרי סטיכלינג מסוג 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$
נוסחת נסיגה למספרי סטיכלינג לא מסומנים מסוג 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)$
$\binom{-1/2}n=\left(\frac{-1}4\right)^n\binom{2n}n$
$\forall n\in\mathbb N:\ \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}$