על שלוש זהויות, אינבולוציות הופכות סימן ומשפט מקמהון

היום אדבר על 3 זהויות קומבינטוריות, שכולן יהיו מקרים פרטיים של הסכום הבא:

S(n,s) = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}^{s}

עבור s=1,2,3. מסתבר שעבור ערכים אלו של s יש ייצוג פשוט לסכום, וההוכחה תהיה קומבינטורית ותשתמש באינבולוציה הופכת סימן, רעיון קומבינטורי מגניב ופשוט ששימושי בעוד הרבה זהויות נוספות.

בנוסף לפתרונות הקומבינטוריים נציג גם פתרונות אלגברים, ביניהם: שימוש בבינום של ניוטון, פונקציות יוצרות ויצוג אינטגרלי. צריך לזכור שיש הרבה זהויות שתחילה הוכחו באופן אלגברי ורק לאחר מכן גילו להן פירוש קומבינטורי.

המקרים s=1,2 יחסית פשוטים, אבל המקרה s=3 יהווה לנו אתגר שנדאג לפתור במגוון דרכים, כולל קומבינטורית עם אינבולוציה.

לשתי הוכחות של המקרה s=3, שנקרא 'זהות Dixon', אקדיש חלק נכבד ונפרד בפוסט. מדובר בהוכחות שנובעות מתוצאות לא פשוטות – אחת היא השערת Dyson והשנייה היא משפט המאסטר של MacMahon. נציג מספר הוכחות למשפט MacMahon, ביניהן הוכחה קומבינטורית באמצעות אינבולוציה, וזה לדעתי יהיה שיא הפוסט.

לאורך כל הפוסט שיבצתי תרגילים, ביניהם הכללות של הזהויות שעליהן נסוב הפוסט, אבל גם תוצאות מרשימות ולא-טריוויאליות – נסו ידכם בהן! אשמח לשמוע על פתרונותכם. לשאלות יש פתרונות בעזרת אינבולוציות, אבל יתכנו כמובן פתרונות אחרים.

המקרה s=1

במקרה זה,

S(n,1)=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k} = \delta_{0,n} = \begin{cases} 0 & n>0\\ 1 & n=0 \end{cases}

המקרה n=0 ברור (זכרו ש-\binom{x}{0} = 1).

פיתרון א' – הבינום של ניוטון

אחת הזהויות החשובות בקומבינטוריקה היא הבינום של ניוטון, שמסביר איך נראה הבינום X+Y כשמעלים אותו בחזקת n ופותחים סוגריים:

(X+Y)^{n} = \sum_{k=0}^{n}\binom{n}{k}X^{k}Y^{n-k}

כאשר \binom{n}{i} הם המקדמים הבינומיים המוכרים ממשולש פסקל. אם נציב Y=1,X=-1, נקבל: (1-1)^{n}=S(n,1), כלומר S(n,1)=0^{n}=\delta_{0,n}.

דרך קצת אחרת להסתכל על הוכחה זו היא להתחיל עם (1+X)^{n}=\sum_{k=0}^{n}\binom{n}{k}X^{k} ואז להציב X=-1. אפשר להגיד שזו הוכחה עם פונקציות יוצרות: (1+X)^{n} היא הפונקציה היוצרת של המקדמים הבינומים, ואנחנו רוצים לסכום אותם עם סימנים מתחלפים, כלומר להציב X=-1.

תרגיל 1: חשבו במפורש את S_{0}=\sum_{2|k}\binom{n}{k},S_{1}=\sum_{2\nmid k}\binom{n}{k} (שימו לב שS(n,1)=S_{0}-S_{1}). בדומה, חשבו את \sum_{k\equiv a\mod b}\binom{n}{k} וחשבו את המרחק שלו מ-\frac{2^n}{n}. (רמז: השתמשו בסכום \sum_{k}\omega^{k}\binom{n}{k} כאשר \omega שורש יחידה מסדר b).

פיתרון ב' – אינדוקציה

נשתמש בזהות פסקל \binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}
כדי לכתוב את הסכום ה-n+1 כתלוי בסכום ה-n:

\begin{aligned} \sum_{k=0}^{n+1}(-1)^{k}\binom{n+1}{k} &= \sum_{k=0}^{n+1}(-1)^{k}\binom{n}{k}+\sum_{k=0}^{n+1}(-1)^{k}\binom{n}{k-1} \\  &= \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}+(-1)^{n+1}\binom{n}{n+1}-\sum_{k=0}^{n+1}(-1)^{k-1}\binom{n}{k-1} \end{aligned}

כלומר S(n+1,1)=S(n,1)+0-S(n,1)=0. זה נכון לכל n \ge 0. בדיקה ש-S(0,1) = 0 משלימה את ההוכחה.

תרגיל 2: \sum_{k=0}^{r}(-1)^{k}\binom{n}{k}=(-1)^{r}\binom{n-1}{r}.

פיתרון ג' – אינבולוציה

כעת נציג את הפיתרון הקומבינטורי. הרעיון הוא לתת פירוש קומבינטורי לכל איבר (לא כולל הסימן (-1)^k), ולזווג בין אובייקטים שנספרים עם סימן שונה. נקבע קבוצה A=\{1,2,\cdots, n\} בעלת n \ge 1 איברים. \binom{n}{k} סופר תתי-קבוצות של A מגודל k.

נגדיר את הפונקציה הבאה, מ-P(A)=\{\text{subsets of A} \} לעצמה:

f(X)=\begin{cases} X\cup\{n\} & n\notin X\\ X\setminus\{n\} & n\in X \end{cases}

אפשר להבחין ש-f מקיימת f(f(X))=X, כלומר f היא אינבולוציה – פונקציה שהופכית לעצמה. פונקציה כזו היא בפרט פרמוטציה, ומעגליה הם בגודל 1 (נקודות שבת) או 2 (חילופים). במקרה שלנו, ל-f אין נקודות שבת. f שלנו מקיימת תכונה חשובה: (-1)^{|f(X)|}=-(-1)^{|X|}, כלומר היא הופכת את הסימן (או ה"משקל") של X. אינבולוציה כזו תיקרא אינבולוציה הופכת סימן. אפשר לכתוב את הסכום בצורה הבאה:

\begin{aligned} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k} &= \sum_{X\in P(A)}(-1)^{|X|} \\ &= \sum_{\{X,f(X)\}\subset P(A)}(-1)^{|X|}+(-1)^{|f(X)|} \\ &= \sum_{\{X,f(X)\}\subset P(A)}((-1)^{|X|}-(-1)^{|X|}) \\ &= 0 \end{aligned}

ובמילים: במקום לסכום על איברי P(A), אנחנו סוכמים על זוגות זרים בP(A) של קבוצה X וה-f שלה, f(X). כל זוג כזה תורם אפס לסכום. \blacksquare.

טיעון זה נופל כאשר n=0, כי אז אי-אפשר להגדיר f בצורה שהגדרנו.

תרגילים נוספים

כעת – מספר תרגילים, כאשר הראשון שבהם מוסיף פרמטרים נוספים לזהות שזה עתה הוכחנו.

תרגיל 3 – הכללה וגזירה:

i. הוכיחו את ההכללה הבאה של הסכום שחישבנו:

\sum_{k=0}^{i}\binom{i}{k}\binom{k}{j}(-1)^{k+i}=\delta_{i,j}

(עבור j=0 זו הזהות שהוכחנו). מצאו הוכחה עם אינבולוציה הופכת סימן אבל גם הוכחה אלגברית.

ii. הוכיחו את ההכללה הבאה של הסעיף הקודם בעזרת אינבולוציה הופכת סימן:

\sum_{k=0}^{i}(-1)^{k+i}\binom{i}{k}\binom{k+m}{j}=\binom{m}{j-i}

מצאו גם הוכחה באינדוקציה ישירה מזהות פסקל.

iii.  יהי f פולינום ממעלה d. הראו שהסכום (\Delta_{i}f)(x)=\sum_{k=0}^{i}(-1)^{i+k}\binom{i}{k}f(x+k) מתאפס עבור i>d, ועבור i=d הוא בדיוק d! כפול המקדם המוביל של f. (סכום זה הוא הנגזרת הדיסקרטית ה-i-ית של f ב-x, עוד עליו תמצאו בפוסט הזה. הזהות שהוכחנו על S(1,n) שקולה לכך שהנגזרת הדיסקרטית ה-i-ית של הפונקציה הקבועה 1 מתאפסת עבור i>1).

תרגיל  4 (מטריצת ונדרמונדה): נסמן ב-A את המטריצה n \times n שמורכבת מהאיברים a_{i,j}=x_{i}^{j},0\le i,j\le n-1. הראו, באמצעות אינבולוציה, ש-\det A=\prod_{i>j}(x_{i}-x_{j}). השתמשו בנוסחה המפורשת לדטרמיננטה.

(רמז: חשבו על הקשר בין גרפים מכוונים שלמים על n קודקודים לבין מונום בדטרמיננטה)

תרגיל 5 (הכלה-הדחה): הוכיחו את עיקרון הכלה-הדחה באמצעות אינבולוציה:

|\cup_{i=1}^n A_i | = \sum_{k = 1}^{n} (-1)^{k+1} \left( \sum_{1 \leq i_{1} < \cdots < i_{k} \leq n} \left| A_{i_{1}} \cap \cdots \cap A_{i_{k}} \right| \right)

המקרה s=2

במקרה זה,

\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}^{2} = \begin{cases} (-1)^{n/2}\binom{n}{n/2} & 2|n\\ 0 & 2\nmid n \end{cases}

המקרה n=0 שוב ברור. כש-n אי-זוגי, האיבר ה-k מבטל את האיבר ה-n-k ולכן התוצאה היא אפס. אפשר להסביר זאת בשפה של אינבולוציות הופכות סימן: \binom{n}{k}^{2} סופר זוגות סדורים (X,Y) של תתי-קבוצות של A=\{ 1,2,\cdots, n\} בגודל k. הפונקציה f(X,Y)=(A\setminus X,A\setminus Y) היא אינבולוציה על זוגות (X,Y) של  תתי-קבוצות של A באותו גודל, ול-f אין נקודות שבת. בנוסף, f הופכת סימן (כי n אי-זוגי). לכן, כמו במקרה s=1, הסכום מתאפס. ל-n זוגי טיעון זה קורס – זה עדיין אינבולוציה, אך היא לא הופכת סימן.

נמצא קודם הוכחה אלגברית.

הוכחה א' – הבינום של ניוטון, פעמיים

(1+X)^{n}(1-X)^{n} שווה מצד אחד ל-(1-X^{2})^{n}=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}X^{2k} ומצד שני ל-(\sum\binom{n}{i}X^{i})(\sum(-1)^{j}\binom{n}{j}X^{j})=\sum_{k}(\sum_{i+j=k}(-1)^{j}\binom{n}{j}\binom{n}{i})X^{k}. כעת נשווה את המקדם של X^n בשתי ההצגות.

תרגיל 6:

i. הראו ש-

\sum_{i+j=k}(-1)^{i}\binom{n}{i}\binom{n}{j}=\begin{cases} (-1)^{k/2}\binom{n}{k/2} & 2|k\\ 0 & 2\nmid k \end{cases}
.

ii. נניח שn \ge m. הראו ש\sum_{k}(-1)^{k}\binom{n}{k}\binom{m}{k}=\sum_{i+2j=m}\binom{n-m}{i}(-1)^{j}\binom{m}{j}.

הוכחה ב' – אינבולוציה

הפעם האינבולוציה פחות טריוויאלית. כרגיל, נקבע קבוצה A=\{1,2,\cdots,n\} בעלת n \ge 1 איברים. \binom{n}{k}^{2} סופר זוגות סדורים (X,Y) של תתי-קבוצות של A בגודל k. עבור זוג קבוצות X,Y נגדיר את Z להיות האיחוד של חיתוך X,Y עם חיתוך המשלימים, כלומר: (X\cap Y)\cup(X^{c}\cup Y^{c}). נגדיר את האינבולוציה הבאה על זוגות תתי-קבוצות של A באותו גודל:

f(X,Y)=\begin{cases} (X-\{\max Z\},Y-\{\max Z\}) & \max Z\in X\cap Y\\ (X\cup\{\max Z\},Y\cup\{\max Z\}) & \max Z\in X^{c}\cap Y^{c} \end{cases}

ובמילים: נסתכל על האיבר הגדול ביותר של Z שלא נמצא בדיוק בקבוצה אחת מבין (X,Y).

יש שני מקרים: אם הוא נמצא בחיתוך של הקבוצות, נוציא אותו מכל אחת מהן, ונקבל זוג חדש, עם k-1 איברים בכל קבוצה.

אם הוא נמצא בחיתוך של המשלימים (מחוץ לשתי הקבוצות), נוסיף אותו לשתיהן, ונקבל זוג חדש עם k+1 איברים בכל קבוצה.

דוגמא: n=4, X=\{1,2 \}, Y= \{1,4\}. הקבוצה Z יוצאת \{ 1, 3\}, ולכן נוסיף את 3 לשתי הקבוצות.

אפשר לוודא שזו אינבולוציה הופכת סימן, אבל יש פרט אחד חסר: מה עושים במקרה שX=Y^c? במקרה זה, החיתוך ריק וגם חיתוך המשלימים ריק… מקרה זה יתכן רק כאשר |X|=|Y|=\frac{n}{2}. במקרה זה, פשוט נגדיר את (X,Y) להיות נקודת שבת של f. למעשה, נקודות השבת הן בדיוק מה שאנחנו צריכים לספור, כי את כל השאר אפשר לזווג לביטויים שתורמים אפס:

\begin{aligned} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}^{2} &= \sum_{(X,Y)\subseteq P(A),|X|=|Y|}(-1)^{|X|} \\ &= \sum_{\text{pairs of }(X,Y),f(X,Y)=(X',Y')}(-1)^{|X|}+(-1)^{|X'|}+\sum_{\text{fixed points of }f:f(X,Y)=(X,Y)}(-1)^{|X|} \\ &= \sum_{f(X,Y)=(X,Y)}(-1)^{|X|} \end{aligned}

אבל לא קשה לספור את נקודות השבת – פשוט זוגות של קבוצה בגודל \frac{n}{2} והמשלים שלה,  לכולן יש אותו סימן והוא (-1)^{\frac{n}{2}}. לכן, במקרה הזוגי, הסכום הוא \binom{n}{n/2}(-1)^{n/2}. במקרה האי-זוגי אין נקודות שבת והסכום הוא 0.

הערה: אפשר לשים לב שכל הגורמים שלא מתבטלים באים מהגורם של k=n/2: (-1)^{n/2}\binom{n}{n/2}^{2}, כי הוא היחיד שסופר קבוצות בגודל n/2 שהן המועמדות היחידות להיות נקודות השבת. עם זאת, רוב המשקל שלו מתקזז עם שאר הגורמים! הקיזוז הוא משמעותי, כי הגורם האמצעי לבדו שווה לריבוע התוצאה.

תרגילים נוספים

תרגיל 7 – וריאציות ופולינומי לז'נדר:

i. הראו ש-\sum_{k=0}^{2n} \binom{n}{k}^2 = \binom{2n}{n}.

ii. הראו כי

\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{n}{k+a}=\begin{cases} (-1)^{(n+a)/2}\binom{n}{(n+a)/2} & 2|n+a\\ 0 & 2\nmid n+a \end{cases}

iii. נסמן a_{n}(x)=\sum_{k=0}^{n}\binom{n}{k}^{2}x^{k}חישבנו את a_n(1) ואת a_n(-1)באופן כללי, a_{n}(x)=(1-x)^{n}P_{n}(\frac{1+x}{1-x}), כאשר:

P_{n}(x)=2^{-n}\sum_{k=0}^{n}\binom{n}{k}^{2}(x-1)^{n-k}(x+1)^{k}

הוא פולינום לז'נדר ה-n-י.
הפולינומים הללו מקיימים תכונות רבות, נסו להוכיח את חלקן:

  • הם אורתוגונלים לפי המכפלה הפנימית \langle f,g\rangle=\int_{-1}^{1}fgdx, ו-\langle P_{n},P_{n}\rangle=\frac{2}{2n+1}
  • הם מקיימים את הרקורסיה (n+1)P_{n+1}(x)=(2n+1)xP_{n}(x)-nP_{n-1}(x)
  • הם סימטריים או אנטי-סימטריים בהתאם לזוגיות של n, כלומר P_{n}(x)=(-1)^{n}P_{n}(-x).

תרגיל 8 (Reed-Dawson): הראו ש-\sum_{k}\binom{n}{2k}\binom{2k}{k}2^{n-2k}=\binom{2n}{n}. השתמשו בכך כדי להראות:

\sum_{k}\binom{n}{k}\binom{2k}{k}(-2)^{n-k}=\begin{cases} \binom{n}{n/2} & 2|n\\ 0 & 2\nmid n \end{cases}

(רמז לזהות הראשונה: 2 האגפים סופרים מילים באורך n מעל האלף-בית a,b,c,d כך שכמות הa-ים שווה לכמות הb-ים.)

תרגיל 9: נסמן ב-A_k את אוסף ההפרמוטציות על \{1,2,\cdots,n\} המקיימות \sum_{i=1}^{n}|i-\pi(i)|=2k (שימו לב שהסכום זוגי בכל אופן). הראו ש-\sum_{\pi\in A_{k}}\text{sign(\ensuremath{\pi})}=(-1)^{k}\binom{n-1}{k}.

תרגיל 10 – מסלולים ומספרי קטלן:

נסתכל על מסלולים באורך 2n שמתחילים ב(0,0) ומשתמשים בצעדים (1,1),(1,-1) בלבד.

i. הראו שכמות המסלולים שלא יורדים מתחת לציר האיקס היא \binom{2n}{n}.

ii. הראו שכמות המסלולים שלא חוזרים לציר האיקס אחרי הצעד האפס היא \binom{2n}{n}.

iii. הראו שכמות המסלולים שלא יורדים מתחת לציר האיקס ומסיימים ב(2n,0) היא \binom{2n}{n} - \binom{2n}{n+1} (מספרי קטלן).

iv. הוכיחו את הזהות \sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n.

v. הראו כי: \sum_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}(-1)^{k}=2^{n}\binom{n}{n/2} כאשר n זוגי.

תרגיל 11 – קבוצות סכום: יהיו A,B קבוצות זרות של מספרים שלמים אי-שליליים. נגדיר לכל קבוצה C את האוסף הבא: C' = \{ c_1+c_2 | c_1,c_2 \in C, c_1 \neq c_2\} . שימו לב – באוסף, בניגוד לקבוצה, יש משמעות לאיבר שמופיע פעמיים.

i. הראו שאם A'=B' אז |A|=|B|=2^k עבור איזשהו k.

ii. נגדיר את הקבוצות A,B באופן הבא: A מכילה מספרים בין 0 ל-2^k-1 עם מספר זוגי של אחדות בבסיס בינארי, וB מוגדרת בדומה רק עם "אי-זוגי" במקום "זוגי". השתמשו באינבולוציה כדי להראות ש-A'=B'.

תרגיל 12 – אורתוגונליות מספרי סטירלינג: מספרי סטירלינג מהסוג הראשון סופרים כמה פרמוטציות עם בדיוק k מעגלים יש על קבוצה בגודל n\left[{n\atop k}\right].

מספרי סטירלינג מהסוג השני סופרים בכמה דרכים אפשר לחלק קבוצה בגודל n ל-k תתי-קבוצות זרות (שאיחודן הוא הקבוצה המקורית): \left\{ n \atop k \right\}. הראו את הקשר הבא:

\sum_{k=m}^n (-1)^{k+m} \left\{ n \atop k \right\} \left[ k \atop m \right] = \delta_{nm}

המקרה s=3

המקרה הזה מסובך יותר (ויפה יותר) מהקודמים ודורש יותר ריכוז – מומלץ לקחת הפסקה 🙂

במקרה זה,

\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}^{3} = \begin{cases} (-1)^{n/2}\binom{3n/2}{n/2,n/2,n/2} & 2|n\\ 0 & 2\nmid n \end{cases}

זהות זו נקראת זהות Dixon על שם המתמטיקאי הבריטי שהוכיח אותה ב-1891, לאחר שהמתמטיקאי Frank Morley שם לב אליה (והצליח גם להוכיח אותה בדרך אחרת, מאוחר יותר). ההוכחה המקורית שלו היא באמצעות אינטגרל טריגונומטרי, גישה שאפשר להכליל למעשה לכל s. ב-1902 הוא הוכיח הכללה אלגנטית של הזהות שתינתן בתרגילים, הפעם עם אנליזה יותר מורכבת וטורים היפרגיאומטריים. עשרות שנים אח"כ נמצאו הוכחות פשוטות יותר, ביניהן הוכחה בעזרת אינבולוציה.

מעניין לציין שרמנוג'אן גילה את זהות דיקסון גם. הוא כתב עליה (ועל עוד זהויות) במכתב (כנראה בשנת 1913 או קצת אחרי) לחברו הבריטי Hardy, והוא כתב אותה בצורה המעניינת הבאה:

(\sum_{i} \frac{x^i}{i!^3}) (\sum_{j} \frac{(-x)^j}{j!^3}) = \sum_{n} \frac{(3n)!}{n!^3(2n)!^3}(-x^2)^n

הוא לא פירסם הוכחה אבל אפשר להאמין שהוא ידע להוכיח אותה, בזכות השליטה המרשימה שלו בטורים היפרגיאומטריים.

הוכחה א' – אינבולוציה

הפעם נתחיל ישר בהוכחה הקומבינטורית, שהיא מדהימה בעיניי. (בהמשך תהיה הוכחה קומבינטורית נוספת).
למען הפשטות נחליף את n ב-2n:

\sum_{k}(-1)^{k}\binom{2n}{k}^{3} = (-1)^{n}\binom{3n}{n,n,n}

העולם שלנו יהיה עולם המחרוזות המורכבות מהאותיות 1,2,3.

המקדם המולטינומי \binom{3n}{n,n,n} סופר כמה מילים יש באורך 3n עם מספר שווה של האותיות 1,2,3.

מכל מילה כזו, s, ניצור שלשת מילים (s_1, s_2,s_3) באופן הבא: s_i נוצרת מ-s ע"י מחיקת כל המופעים של i. בפרט, אורך s_i הוא 2n.
נשים לב שמתוך (s_{1},s_{2},s_{3}) אפשר לשחזר את s תמיד ובאופן יחיד. איך עושים זאת? אם האות הראשונה של s היא לדוגמא 1, אז 2 המילים s_2, s_3 יתחילו ב-1. לכן, אם נסתכל על האות הראשונה של 3 המילים, האות שתופיע יותר מפעם אחת היא בהכרח האות הראשונה של s. אחרי שחילצנו אינפורמציה זו, נמחק אותה משתי המילים שבהן היא הופיעה ונחזור על התהליך כדי לקבל את האות השנייה, וכו'. כך משחזרים את s.

אם האלגוריתם נכשל, סימן שהגענו לנקודה בה אין אות שמופיעה יותר מפעם אחת. יש 2 מקרים – האותיות המתאימות ב-s_{1},s_{2},s_{3}  הן 2,3,1 או 3,1,2.

עכשיו יש לנו את כל הכלים לבנות את האינבולוציה (חשבו דקה לפני שאתם קוראים הלאה!). האינבולוציה תהיה זו: \binom{2n}{k}^{3} סופר שלשות של מחרוזות (s_{1},s_{2},s_{3}) שמקיימות את התנאים הבאים: s_i מאורך 2n ומכילה k תווים מסוג i+1 ועוד 2n-k מהסוג i+2. ( כמובן שהחיבור הוא מודולו 3, כך ש3+2 = 2, 1+2=3).

נגדיר את האינבולוציה הבאה על שלשות אלו: אם אלגוריתם שחזור המילה המקורית מצליח, השלשה תהיה נקודת שבת של האינבולוציה. אחרת, נתאים לשלשה (s_1, s_2, s_3) שלשה אחרת באופן הבא: נפעיל את האלגוריתם ומתישהו ניכשל כי יהיו 3 אותיות שונות. כאמור, יש 2 מקרים: האותיות הבעייתיות ב-s_{1},s_{2},s_{3} הן (בהתאמה) 2,3,1 או 3,1,2. פשוט נחליף בין 2 המקרים וכך נקבל שלשה אחרת (s'_{1},s'_{2},s'_{3}).

האינבולוציה הופכת סימן (ודאו!) ונקודות השבת הן בדיוק המילים עם n 1-ים, n 2-ים ו-n 3-ים, ויש להן סימן (-1)^n. מכאן נובעת הזהות. \blacksquare

דוגמא: n=2. נבחר s_1=2233, s_2=1133, s_3=1122. האלגוריתם מצליח לשחזר את s=112233. מילה זו נספרת באגף שמאל ב-k=2.
דוגמא שאינה נקודת שבת: כעת נבחר s_{1}=2332,s_{2}=3131,s_{3}=1122. שלשה זו נספרת באגף שמאל ב-k=2. האלגוריתם נכשל כבר בהתחלה. האינבולוציה נותנת את s'_{1}=3332,s'_{2}=1131,s'_{3}=2122, ושלשה זו נספרת באגף שמאל ב-k=3 ועם סימן הפוך.

תרגיל 13: \sum_{k}(-1)^{k}\binom{2n}{k+a}^{3}=(-1)^{a+n}\binom{3n}{n,n,n}.

תרגיל 14: הגרסה המלאה של זהות דיקסון:

 \sum_{k}(-1)^{k}\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}=(-1)^{n}\binom{a+b+c}{a,b,c}

הוכחה ב' – אינטגרל טריגונומטרי

ב-1891, Alfred Cardew Dixon נתן הוכחה מדהימה (שנכנסה בעמוד אחד…) לזהות שלימים נקראה על שמו. ההוכחה שלו מעידה על עליונות טכנית והיכרות טובה עם טורים היפרגיאומטריים ואינטגרלים טריגונומטרים.

החלטתי לא לתת אותה כלשונה כאן. מה שכן אעשה הוא לתת את נקודת המוצא של ההוכחה שלו, שעושה רדוקציה לחישוב אינטגרל טריגונומטרי, ולתת הוכחה שונה שפורסמה שנה לאחר מכן. היא הייתה ברוח ההוכחה של דיקסון אבל התחמקה כליל מאינטגרלים.

הרעיון של דיסקון היה זה: להביע את אגף שמאל של הזהות כמקדם החופשי של איזושהו פולינום לורן – פולינום שמותר שיהיו בו חזקות שליליות, לדוגמא z_{1}^{-1}+2z_{2}z_{3}^{-5}. כל פולינום לורן מתקבל מחלוקה של פולינום במונום.

בהינתן פולינום לורן, אפשר לחלץ את המקדם החופשי שלו בעזרת אינטגרל (אפשר לחלץ כל מקדם למעשה) באופן הבא: אם f(x,y)=\sum a_{i,j}x^{i}y^{j} אז:

a_{0,0} = (\frac{1}{2\pi})^{2}\int_{0}^{2\pi}\int_{0}^{2\pi}f(e^{i\theta_{1}},e^{i\theta_{2}})d\theta_{1}d\theta_{2}

ההוכחה לכך נובעת מכך ש-\frac{1}{2\pi}\int_{0}^{2\pi}e^{ik\theta}d\theta=\delta_{k,0}. התקווה היא שהאינטגרל יהיה פשוט מן הסכום.

במקרה שלנו, הפולינום שניקח הוא f(x,y)=(1+x)^{2n}(1+y)^{2n}(1-\frac{1}{xy})^{2n}. כשפותחים בו סוגריים מקבלים:

\begin{aligned} f(x,y) &= \sum_{ij,k}\binom{2n}{i}x^{i}\binom{2n}{j}y^{j}\binom{2n}{k}(-1)^{k}(xy)^{-k} \\ &= \sum_{i,j,k}\binom{2n}{i}\binom{2n}{j}\binom{2n}{k}x^{i-k}y^{j-k}(-1)^{k} \end{aligned}

והמקדם של x^0 y^0 מתאים ל-i=j=k והוא \sum_{i}\binom{2n}{i}^{3}(-1)^{i} = S(2n,3). כעת נותר לחשב את האינטגרל עצמו – משימה לא קלה כלל. האינטגרל הופך ל:

\begin{aligned} & (\frac{1}{2\pi})^{2}\int_{0}^{2\pi}\int_{0}^{2\pi}(1+e^{i\theta_{1}})^{2n}(1+e^{i\theta_{2}})^{2n}(1-e^{-i(\theta_{1}+\theta_{2})})^{2n}d\theta_{1}d\theta_{2}  \\ &= (\frac{1}{2\pi})^{2}\int_{0}^{2\pi}\int_{0}^{2\pi}(e^{-i\theta_{1}/2}+e^{i\theta_{1}/2})^{2n}(e^{-i\theta_{2}/2}+e^{i\theta_{2}/2})^{2n}(e^{i(\theta_{1}+\theta_{2})/2}-e^{-i(\theta_{1}+\theta_{2})/2})^{2n}d\theta_{1}d\theta_{2}  \\ &= (\frac{1}{2\pi})^{2}\int_{0}^{2\pi}\int_{0}^{2\pi}(8i\cos(\frac{\theta_{1}}{2})\cos(\frac{\theta_{2}}{2})\sin(\frac{\theta_{1}+\theta_{2}}{2}))^{2n}d\theta_{1}d\theta_{2}  \\ &= (-1)^{n}8^{2n}\pi^{-2}\int_{0}^{\pi}\int_{0}^{\pi}(\cos(\theta_{1})\cos(\theta_{2})\sin(\theta_{1}+\theta_{2}))^{2n}d\theta_{1}d\theta_{2} \end{aligned}

כבר קיבלנו את סימן הסכום ללא מאמץ, אבל נעצור כאן. במקום להסביר איך מנצחים את האינטגרל, נדבר על קיצור דרך נהדר של Richmond, שפורסם ב-1892, שנה אחרי דיקסון.

ההבחנה של Richmond: נניח שנתונים לנו 2 פולינומים F(x)=\sum a_i x^i, G(x) = \sum b_j x^j ואנחנו רוצים לחשב את הפולינום שמתקבל מהכפלת המקדמים שלהם איבר-איבר: H(x) = \sum a_i b_i x^{i}. אפשר לעשות זאת באופן הבא: H(x^2) הוא החלק של F(xy)G(xy^{-1}) שלא תלוי ב-y. (ודאו!)

הבחנה זו היא הכללה של המיני-הבחנה הבאה, שמתקבל מהמקורית ע"י הצבת x=1:

מיני-הבחנה: נניח שנתונים לנו 2 פולינומים F(x)=\sum a_i x^i, G(x) = \sum b_j x^j ואנחנו רוצים לחשב את הסכום שמתקבל מהכפלת המקדמים שלהם איבר-איבר: \sum a_i b_i.
סכום זה הוא האיבר החופשי במכפלה F(x) G(x^{-1}).

נשתמש בהבחנה של ריצ'מונד באופן הבא: ניקח את F,G שניהם להיות F(x) = G(x) = \sum (-1)^i \binom{2n}{i}x^i = (1-x)^{2n}. כדי לחשב את הפולינום H(x^2) = \sum \binom{2n}{i}^{2} x^{2i} נכפיל את (1-xy)^{2n} ב-(1-xy^{-1})^{2n} וניקח את המונומים שלא מכילים את y.
מכפלת 2 הפולינומים היא (1-xy)^{2n}(1-xy^{-1})^{2n} = ((1+x^2) - (xy + xy^{-1}))^{2n}, ובעזרת הבינום של ניוטון אנחנו יכולים להביע את המכפלה כך:

\sum_{k} \binom{2n}{k} (1+x^2)^{2n-k}x^{k}(-1)^k (y+y^{-1})^{k}

הגורם החופשי של (y+y^{-1})^{k} הוא 0 אם k אי-זוגי ו-\binom{k}{k/2} אחרת, לכן נסכום על 2k במקום על k והפולינום יוצא:

H(x^2)=\sum_{k} \binom{2n}{2k}\binom{2k}{k} (1+x^2)^{2n-2k} x^{2k}=\sum_{k} \frac{(2n)!}{(2n-2k)!k!k!} (x+x^{-1})^{2n-2k} x^{2n}

כעת, נשתמש במיני-הבחנה, ונשים לב שהסכום \sum_{i} (-1)^{i} \binom{2n}{i}^3 מתקבל מלקחת את המקדם החופשי ב-H(x^2)=\sum \binom{2n}{i}^{2} x^{2i} כפול F(x^{-2}) = (x-x^{-1})^{2n}x^{-2n}=\sum_{i} (-1)^{i} \binom{2n}{i}x^{-2i}. המכפלה יוצאת:

\sum_{k} \frac{(2n)!}{(2n-2k)!k!k!}(x+x^{-1})^{2n-2k}(x-x^{-1})^{2n}

למה: המקדם החופשי של (x+x^{-1})^{2i}(x-x^{-1})^{2j} הוא (-1)^{j} \frac{(2i)!(2j)!}{i!j!(i+j)!}הוכחה: באינדוקציה על iנסמן את המקדם ב-A(i,j). עבור i=0 זה נובע מהבינום של ניוטון. צעד האינדוקציה משתמש בשיוויון (x-x^{-1})^2 + 4 = (x+x^{-1})^2 שנותן את השיוויון:

(x+x^{-1})^{2(i+1)}(x-x^{-1})^{2j} =(x+x^{-1})^{2i} (x-x^{-1})^{2(j+1)}+4(x+x^{-1})^{2i}(x-x^{-1})^{2j}

וממנו מקבלים את הרקורסיה A(i+1,j) = 4A(i,j)+A(i,j+1), שמתקיימת גם ע"י (-1)^{j} \frac{(2i)!(2j)!}{i!j!(i+j)!}\blacksquare

קוריוז: הלמה הזו מוכיחה את שאלה 3 של IMO 1972: "הראו שהביטוי \frac{(2m)!(2n)!}{m!n!(m+n)!} תמיד שלם."

בהינתן הלמה, המקדם החופשי שרצינו נהיה-

(-1)^n \sum_{k} \frac{(2n)!}{(2n-2k)!k!k!} \frac{(2n)!(2n-2k)!}{n!(n-k)!(2n-k)!} = (-1)^n \binom{2n}{n} \sum_{k} \binom{2n}{k} \binom{n}{n-k}

והוכחה מסתיימת כששמים לב שהסכום האחרון הוא בדיוק המקדם של t^n ב-(1+t)^{2n}(1+t)^{n}=(1+t)^{3n}, שהוא \binom{3n}{n}, ו-\binom{2n}{n} \binom{3n}{n} = \binom{3n}{n,n,n}. \blacksquare

הוכחה ג' – שיוויון פולינומיאלי

הוכחה אלגנטית וחדשה (מ-2003) של Victor Guo. נוכיח את השיוויון הבא בין פולינומים:

\sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}\binom{x}{k}\binom{x}{2n-k} = (-1)^{n}\binom{x}{n}\binom{x+n}{n}

נשים לב שאם נציב x=2n נקבל את זהות דיקסון.

שני הפולינומים ממעלה 2n. הרעיון הוא להראות שהם מסכימים על 2n+1 נקודות ולכן שווים זהותית.

שיוויון עבור x=n: יש באגף שמאל איבר אחד בלבד שלא מתאפס והוא מתאים ל-k=n (הדרישות שלנו הן x\ge 2n-k, x \ge k, 2n \ge k). לכן הערך של אגף שמאל הוא (-1)^{n}\binom{2n}{n}\binom{n}{n}\binom{n}{n} וזה שווה לאגף ימין ב-x=n.

שיוויון עבור x=0,1,2,\cdots,n-1: אגף ימין מתאפס, לכן צריך להראות שגם אגף שמאל מתאפס. ואכן, כל המקדמים הבינומים מתאפסים כי \binom{x}{k}\binom{x}{2n-k} מתאפס עבור 0\le x<\max\{k,2n-k\} ובפרט עבור 0\le x<n.

שיוויון עבור x= -1,-2,\cdots, -n: שוב אגף ימין מתאפס – נראה שגם שמאל. נסמן x = -1-y כאשר 0\le y\le n-1. אגף שמאל נהיה:

\begin{aligned} \sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}\binom{x}{k}\binom{x}{2n-k} &= \sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}\binom{-1-y}{k}\binom{-1-y}{2n-k} \\  &= \sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}\binom{y+k}{k}\binom{y+2n-k}{2n-k} \end{aligned}

נסמן P(k)=\binom{y+k}{k}\binom{y+2n-k}{2n-k}. פולינום זה ממעלה y+y=2y ב-k. בפרט, הנגזרת הדיסקרטית ה-2n שלו מתאפסת:

(\Delta_{2n}P)(0)=\sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}P(k)=0

וזה בדיוק הסכום האחרון. \blacksquare

הוכחה ד' – מעגלים בגרפים

נחזור קצת לקומבינטוריקה. Foata הוכיח את הזהות הבאה באופן מקסים:

\begin{aligned} \binom{b+c}{c+k}\binom{c+a}{a+k}\binom{a+b}{b+k} &= \sum_{n} \binom{a+b+c-n}{a-n,b-n,c-n,n+k,n-k} \end{aligned}

קודם נראה מה היא נותנת. אם נכפיל זהות זו ב(-1)^{k} ונסכום על k, נקבל באגף ימין:

\begin{aligned} \sum_{k} (-1)^{k} \sum_{n} \binom{a+b+c-n}{a-n,b-n,c-n,n+k,n-k} &= \sum_{n} \binom{a+b+c-n}{a-n,b-n,c-n,2n} (\sum_{k} (-1)^k\binom{2n}{n-k}) \\ &= \sum_{n} \binom{a+b+c-n}{a-n,b-n,c-n,2n} \delta_{2n,0} \\ &= \binom{a+b+c}{a,b,c} \end{aligned}

ובאגף שמאל נקבל את הסכום:

\sum_{k} (-1)^{k} \binom{b+c}{c+k}\binom{c+a}{a+k}\binom{a+b}{b+k}

כאשר a=b=c זו הזהות המקורית של דיקסון. \blacksquare

Foata הוכיח הזהות שלו באמצעות "פירוק מעגלים": נסתכל על גרפים מכוונים ללא לולאות עם קבוצת הקודקודים \{1, 2, 3\}. לגרפים שלנו תהיה תכונה נוספת: על הצלעות היוצאות מקודקוד ספציפי יהיה יחס סדר. במילים אחרות, נמספר את הצלעות היוצאות מכל קודקוד (אם דרגת היציאה היא d, אז נמספר את הצלעות 1,2,\cdots ,d).
הערה: אם יש יותר מצלע אחת מקודקוד אחד לקודקוד אחר, לא תהיה לנו דרך להבדיל בין המצבים.

נסתכל ספציפית על גרפים שבהם דרגת הכניסה שווה לדרגת היציאה, כלומר בגרף יש מסלול אוילר וקיימת הצגה של הגרף כאיחוד של מעגלים זרים.

כעת, נספור בשתי דרכים את כמות הגרפים הממוספרים עם מטריצת שכנויות כזו:

\begin{bmatrix} 0 & c+k & b-k \\ c-k & 0 & a+k\\ b+k & a-k & 0 \end{bmatrix}

דרך א' (אגף שמאל): מקודקוד 1 יוצאות (c+k)+(b-k) = c+b צלעות. כדי למספר/לסדר אותן, צריך לבחור בעצם מתוך המספרים 1,2,\cdots, c+b מי יהיה שייך לצלע 1 \to 2 ומי ל-1 \to 3. כמות המספורים היא \binom{b+c}{c+k}. נפעיל אותו שיקול על 2 הקודקודים הנותרים כדי לקבל שמספר הגרפים הוא מכפלה של שלושה מקדמים בינומיים, בדיוק אגף שמאל של הזהות שכתבנו בהתחלה.

דרך ב' (אגף ימין): כמו שאמרנו כבר, יש פירוק למעגלים. בגלל שהגרף ללא לולאות, יש 5 מעגלים בסיסיים:

c_1 = 1\to 2 \to 1 = [12], c_2 = 1 \to 3 \to 1 = [13], c_3 = 2 \to 3 \to 2 = [23]

c_4 = 1 \to 2 \to 3 \to 1 = [123], c_5 = 1 \to 3 \to 2 \to 1 = [132]

גרפים עם אותה מטריצת שכנויות אבל מספור שונה אפשר לפרק למעגלים באופן שונה. נשתמש באלגוריתם החח"ע הבא:

1. צריך לבחור קודקוד. נבחר את הקודקוד שיש עליו מעגל שכל צלעותיו ממסופרות 1 – תמיד יהיה כזה, והוא יחיד.

2. מורידים את הצלעות של המעגל, ושמים את המעגל הזה בסוף רשימת המעגלים שלנו.

3. לכל קודקוד שהיה במעגל, אנחנו מקטינים את המספרים על הצלעות שיוצאות ממנו ב-1 (כדי ששוב תהיה צלע שמספרה 1). אם נשארו צלעות, חוזרים לסעיף 1.

באופן כזה, 8 הפירוקים הבאים למעגלים הם בעלי אותה מטריצת שכנויות אבל מספור שונה:

[12][13][23], [12][23][13], [13][12][23],[13][23][12],[13][12][23],[23][13][12],[23][12][13],

[123][132],[132][123]

אפשר לראות גם שכל פירוק הוא חוקי: בהינתן רשימת מעגלים, אני יכול לשחזר את הגרף מתוכם וגם את המספור. למה? את הדרגות אפשר לשחזר מתוך ספירת מעגלים, ואת המספור מתוך זה שפשוט נתחיל לבנות את הצלעות ע"י קריאת המעגלים משמאל לימין.

לכן אפשר לספור את הגרפים לפי המעגלים ולא לפי המספורים. נניח שיש e_i מעגלים מסוג c_i. אנחנו מקבלים את המשוואות הבאות מתוך מטריצת השכנויות:

\# 1\to 2 = c+k = e_1 + e_4

\# 1\to 3 = b-k = e_2 + e_5

\# 2\to 1 = c-k = e_1 + e_5

\# 2\to 3 = a+k = e_3 + e_4

\# 3\to 1 = b+k = e_2 + e_4

(יש עוד משוואה אבל היא תלויה באחרות.) אם נסמן n=c-e_1, נקבל:

e_2 = b-n, e_3 = a-n, e_4 = n+k, e_5 = n-k

כמות הגרפים הממוספרים עם e_i מעגלים מסוג c_i יוצאת:

\binom{e_1 + \cdots + e_5}{e_1, e_2, \cdots, e_5} = \binom{a+b+c-n}{a-n,b-n,c-n,n+k,n-k}

(כי כמו שאמרנו, כל סדר של המעגלים מתאים למספור שונה, ולהיפך.) אם נסכום על n נקבל את אגף ימין. \blacksquare

נכליל גישה זו בהמשך כדי להוכיח תוצאה בשם משפט מקמהון.

תרגילים

תרגיל 15: הוכיחו את 2 הוריאציות הבאות:

\sum_{k} (-1)^{k} \binom{b+c+1}{c+k} \binom{c+a+1}{a+k}\binom{a+b+1}{b+k} = 0

\sum_{k} (-1)^{k} k\binom{b+c+1}{c+k} \binom{c+a+1}{a+k}\binom{a+b+1}{b+k} = \frac{(a+b+c+1)!}{a!b!c!}

תרגיל 16 (הכללה q-נומית): יהי q משתנה. נסמן [n]_{q}=\frac{q^{n}-1}{q-1} ונגדיר [n]!_{q}=\prod_{i=1}^{n}[i]_{q} וגם \left[_{m}^{n}\right] = \frac{[n]!_{q}}{[m]!_{q}[n-m]!_{q}}. הוכיחו את הזהות הבאה (עבור q=1 מקבלים את זהות דיקסון):

\sum_{k}(-1)^{k}q^{(3k^{2}+k)/2}\left[_{a+k}^{a+b}\right]\left[_{b+k}^{b+c}\right]\left[_{c+k}^{c+a}\right] = (-1)^{n}\frac{[a+b+c]!_{q}}{[a]!_{q}[b]!_{q}[c]!_{q}}

בפוסט הבא נשתמש באינטגרל של דיקסון כדי לתת קירוב אסימפטוטי לS(2n,s) עבור s כללי. בפרט נראה מהקירוב ל-S(2n,4) שהוא לא שווה ל-\binom{4n}{n,n,n,n}(-1)^{n}, כמו שאפשר לנחש (ולטעות). לדוגמא, בקירוב האמיתי מופיע הקבוע \cos( \frac{\pi}{8} ) = \frac{\sqrt{2 + \sqrt{2}}}{2} שלא מופיע בקירוב סטירלינג.

חילוץ מקדמים – השערת Dyson ומשפט המאסטר

ניתן עוד 2 דרכים מרשימות להוכיח את זהות דיקסון: השערת דייסון, ומשפט המאסטר.
אלו דרכים אלגבריות, אם כי למשפט המאסטר נציג גם הוכחה קומבינטורית.

השערת Dyson

המתמטיקאי-פיזיקאי דייסון פרימן ניסח ב-1962 את ההשערה הבאה לגבי פולינומי לורן (מקורה בפיזיקה סטטיסטית): יהיו a_1, \cdots, a_n מספרים שלמים אי-שליליים. המקדם החופשי של \prod _{1\le i, j\le n, i \neq j}(1-t_i/t_j)^{a_i} שווה למקדם המולטינומי \binom{a_1 + \cdots + a_n}{a_1, a_2, \cdots, a_n}.

פרימן דייסון. אני רוצה לחשוב שזה המשרד שלו, ושיש לו כ"כ הרבה ספרים שהוא נאלץ לצבור אותם על הרצפה.

ההשערה הוכחה עוד באותה שנה, אבל רק 8 שנים אח"כ I. J. Good מצא את ההוכחה הקצרצרה הבאה:

הכללה של זהות פסקל למקדמים מולטינומים מראה כי:

\binom{a_1 + \cdots + a_n}{a_1, \cdots, a_n} = \sum_{i=1}^{n} \binom{a_1 + \cdots + a_{i-1} + (a_i-1) + a_{i+1} + \cdots + a_n}{a_1,\cdots, a_{i-1},a_{i}-1,a_{i+1},\cdots, a_n}

במפתיע, גם הפולינום לורן F(a_1, \cdots, a_n) = \prod _{1\le i\ne j\le n}(1-t_i/t_j)^{a_i} מקיים את אותה רקורסיה, כלומר:

F(a_1, \cdots, a_n) = F(a_1-1,a_2,\cdots,a_n) + \cdots + F(a_1, a_2, \cdots, a_{n-1}, a_n-1)

לאחר צמצום זה שקול לזהות המגניבה 1 = \sum_{j} \prod_{i \neq j} (1-\frac{t_j}{t_i})^{-1}. אפשר להוכיח אותה בדרכים שונות. הדרך הכי קצרה שאני מכיר היא לקחת את הפולינום הקבוע 1, ולעשות לו אינטרפולציית לגראנז' דרך הנקודות (t_i,1), ואז להציב 0 בביטוי המתקבל. זה קסם שכדאי לנסות.

אם הפולינומים F(a_1,\cdots,a_n) מקיימים את הרקורסיה, אז גם המקדמים החופשיים שלהם, ולכן יש לנו את כל התנאים להוכחה אלגנטית באינדוקציה. צריך רק לטפל במקרה שאחד מה-a_i שווה 0, כי אז הרקורסיה לא מוגדרת היטב.
אפשר לראות שהמקדם החופשי במקרה הזה שווה למקדם החופשי של הפולינום ב-n-1 משתנים, בלי t_i נגיד, ולכן פשוט נכניס לאינדוקציה גם את מספר המשתנים. \blacksquare

איך השערת דייסון עוזרת לנו? מסתבר שהמקרה n=3 שקול לזהות דיקסון! בואו נחשב:

\begin{aligned} &\prod_{1 \le i,j \le 3, i \neq j} (1-\frac{t_i}{t_j})^{a_i} \\ &= (-1)^{a_1 + a_2+a_3} {t_1}^{a_1 - a_3} {t_2}^{a_2 - a_1} {t_3}^{a_3-a_2} (1-\frac{t_2}{t_1})^{a_1 + a_2} (1-\frac{t_3}{t_2})^{a_2 + a_3} (1-\frac{t_1}{t_3})^{a_3+a_1} \end{aligned}

ונמשיך עם פתיחת סוגריים חסרת מעצורים:

\sum_{i,j,\ell} (-1)^{a_1+a_2+a_3+i+j+\ell} {a_1+a_2 \choose i} {a_2+a_3 \choose j} {a_3+a_1 \choose \ell} t_1^{\ell-i+a_1-a_3} t_2^{i-j+a_2-a_1} t_3^{j-\ell+a_3-a_2}

האיבר החופשי מתאים ל-i,j,l שמקיימים (l-a_3)+(a_1-i)=0, (i-a_1)-(j-a_2)=0,(j-a_2)+(a_3-l)=0, כלומר (i,j,l) =(k+a_1,k+a_2,k+a_3), ולכן האיבר החופשי שווה ל:

\sum_k (-1)^{2a_1+2a_2+2a_3+3k} {a_1+a_2 \choose a_1+k} {a_2+a_3 \choose a_2+k} {a_3+a_1\choose a_3+k} = \sum_k (-1)^{k} {a_1+a_2 \choose a_1+k} {a_2+a_3 \choose a_2+k} {a_3+a_1\choose a_3+k}

מצד שני, לפי השערת דייסון, סכום זה שווה ל-\binom{a_1 + a_2 + a_3}{a_1, a_2, a_3}.

תרגיל 17: הראו את השיוויון הבא:

\sum_{j=1}^{n} \frac{a_{j}^{k}}{\prod_{i \neq j} (a_j-a_i)} = \begin{cases} 0 & 0 \le k \le n-2 \\ 1 & k=n-1 \end{cases}

תרגיל 18 (Gessel and Stanton): בתרגיל זה נספק עוד הוכחה לזהות דיקסון.

נתחיל בלמה: יהי f(x_1, \cdots, x_n) טור לורן (טור חזקות עם מספר סופי של חזקות שליליות). נסמן ב-CT f את האיבר החופשי שלו (מלשון Constant Term). הראו כי:

CT f(\frac{x_1}{1+x_2},\frac{x_2}{1+x_3},\cdots, \frac{x_n}{1+x_1} ) = CT \frac{ f(x_1, \cdots, x_n) }{1- x_1 x_2 \cdots x_n}

(רמז: מלינאריות, מספיק לבדוק שיוויון עבור f-ים שהם מונומים. השתמשו ב-(1+x)^{m} = \sum_{i \ge 0} x^i \binom{m}{i}, שימו לב שיש שיוויון גם עבור m שלילי.)

כעת, הפעילו את הלמה על \frac{(x-y)^{2n}}{(xy)^{2n}(1-xy)^{2n}} וקבלו את זהות דיקסון.

משפט המאסטר של MacMahon

המתמטיקאי ואיש הצבא הבריטי Percy MacMahon הוכיח ב-1915 משפט בקומבינטוריקה שהיה כ"כ שימושי שהוא קרא לו "משפט מאסטר". הניסוח הוא כזה: תהי A מטריצה ריבועית עם כניסות a_{i,j}, 1\le i,j \le m.

נסמן ב-G(k_1, \cdots, k_n) את המקדם של \prod_{i=1}^{n} x_i^{k_i} במכפלה הבאה:

\prod_{i=1}^n \bigl(a_{i1}x_1 + \dots + a_{in}x_n \bigl)^{k_i}

מסתבר שאפשר לחשב את הפונקציה היוצרת של G! נגדיר את המטריצה האלכסונית T, שעל אלכסונה n משתנים, t_1, \cdots, t_n.  הפונקציה היוצרת של G היא:

\sum_{(k_1,\dots,k_n} G(k_1,\dots,k_n) \, t_1^{k_1}\cdots t_n^{k_n} \, = \, \frac{1}{\det (I - TA)}

Percy Alexander MacMahon. גם איש צבא, גם מתמטיקאי. (עתודאי?)

דוגמאות פשוטות

אם לוקחים מטריצה שכולה אחדות, הדטרמיננטה יוצאת 1-\sum t_i, והמשפט נותן את הזהות (1-\sum t_i)^{-1} = \sum \binom{k_1 + \cdots + k_n}{k_1,\cdots, k_n} \prod t_i^{k_i}.

אם לוקחים מטריצה אלכסונית מקבלים את השיוויון \prod (1-d_i t_i)^{-1} = \sum \prod d_i^{k_i} t_{i}^{k_i}.

בינתיים לא קיבלנו תוצאה מעניינת, אבל לפחות מצאנו 2 דוגמאות בהן הוא עובד…

זהות דיקסון מתוך משפט המאסטר

כעת נראה איך בקלות מקבלים מהמשפט את זהות דיקסון. בהוכחה המקורית של דיקסון, ראינו שאנחנו רוצים לחשב את המקדם החופשי של ((1+x)(1+y)(1-\frac{1}{xy}))^{2n}. במקום הפולינום הזה יכלנו להחליף סימנים ולהשתמש בפולינום הבא: F(x,y)=((1-x)(1-y)(1-\frac{1}{xy}))^{2n}.

המקדם החופשי שלו הוא המקדם של (xy)^{2n} ב-((1-x)(1-y)(xy-1))^{2n}. נעשה שינוי משתנים שהופך את הפולינום להומוגני: x=\frac{x_1}{x_2}, y=\frac{x_2}{x_3}, ומקבלים שאנחנו צריכים את המקדם של (x_1 x_2 x_3)^{2n} ב-(x_2-x_1)^{2n}(x_3-x_2)^{2n}(x_1 - x_3)^{2n} = (x_2-x_3)^{2n}(x_3-x_1)^{2n}(x_1 - x_2)^{2n}, וזה בדיוק מסוג הבעיות שהמשפט פותר. המטריצה המתאימה היא A = \begin{bmatrix} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{bmatrix}, והדטרמיננטה יוצאת:

\det \begin{bmatrix}1 & -t_1 & t_1 \\ t_2 & 1 & -t_2 \\ -t_3 & t_3 & 1 \end{bmatrix} = 1+ t_1 t_2 + t_1 t_3 + t_2 t_3

לכן הפונקציה יוצרת היא \sum_{k} (-1)^{k} \bigl(t_1 t_2 + t_1 t_3 +t_2t_3\bigr)^{k} והמקדם של (t_1 t_2 t_3)^{2n} אכן יוצא (-1)^{n} \binom{3n}{n,n,n} (התרומה מגיעה מ-k=3n).

בספרו של מקמהון, Combinatory Analysis Vol. 1, יש עוד דוגמאות לשימושי המשפט בחקר הפרמוטציות. למעשה שם המשפט מגיע מהציטוט הבא מהספר: "This is a master theorem in the Theory of Permutations". המשפט שימושי בטירוף בספירת פרמוטציות עם אילוצים. למעשה, לא רק פרמוטציות על קבוצות אלא גם על רבי-קבוצות (באנגלית- Multiset).

נציג ונפתור את השאלה המוכרת הבאה: "כמה פרמוטציות יש ללא נקודות שבת?".יש הרבה גישות לפתור שאלה זו (ביניהן: הכלה-הדחה ואינדוקציה), ואני אציג את הגישה של מקמהון. דרך אלגברית לנסח את זה היא: מה המקדם של x_1 x_2 \cdots x_n במכפלה הבאה:

(x_2 + x_3 + \cdots + x_n)(x_1 + x_3 + x_4 + \cdots + x_n) \cdots (x_1 + x_2 + \cdots + x_{n-1})

מקמהון הרחיב את השאלה לשאלה הבאה: נניח ויש לי את ה-Multiset שבו המספר i מופיע a_i פעמים כאשר 1 \le i \le n. כמה פרמוטציות על ה-Multiset הזה ישנן בלי נקודות שבת? בדומה למקרה הקודם, מדובר במקדם של \prod x_i^{a_i} במכפלה \prod_{i} (\sum_{j \neq i} x_j)^{a_i}. זו לא אבחנה טריוויאלית ואני אתן לכם לעכל אותה בעצמכם. משפט מקמהון נותן לי את הפונקציה היוצרת של המקדמים הללו: המטריצה שאני אבחר מורכבת מאפסים על האלכסון ו-1 מחוץ לאלכסון, שתסומן J-I, כאשר J מטריצה שכולה אחדות. הדטרמיננטה \det(I-TA) יוצאת:

1-\sum_{i<j}t_i t_j - 2\sum_{i<j<k}t_i t_j t_k -\cdots - (n-1)t_1 \cdots t_n

והפונקציה היוצרת היא ההופכית שלה. כל שנותר הוא לחלץ את המקדמים, וזה לא כזה נורא, פשוט דורש הרבה התעסקות טכנית עם פונקציות סימטריות. תרגיל קטן כדי שתבדקו שאתם עוקבים: מה הפירוש הקומבינטורי של בחירת המטריצה להיות כולה אחדות (את החישוב כבר עשינו)?

למשפט מקמהון יש הרבה הוכחות קונספטואליות. הכוונה שלי היא להוכחות מהצורה: "טוב, אם נסתכל על זה קצת אחרת זה בעצם מקודד עובדה בסיסית וזה לא כזה מפחיד". בין ההוכחות הללו אפשר למצוא:

  • הוכחה באמצעות פירוש מאלגברה לינארית – אני אדבר עליה קצת. (יש לה גם משמעות בפיזיקה)
  • הוכחה באמצעות היפוך לגראנז' רב-משתנים – אני אדבר עליה קצת.
  • הוכחה באמצעות התורה של פרמוטציות על רבי-קבוצות – לא אתן אותה בדיוק, אבל כן אתן הוכחה דומה עם אינבולוציה הופכת סימן.

אני אתחיל דווקא בהוכחה המקורית של מקמהון, שלצערי היא לא מאוד קונספטואלית. להיפך – היא בעיקר חישובית. ודווקא בגלל זה היא קלה לזכירה.

ההוכחה המקורית: מקמהון הגדיר X_i = \sum_{j} a_{i,j}x_{j}. הביטוי G(k_1,\cdots,k_n) הוא המקדם של \prod x_i^{k_i} ב-\prod X_{i}^{k_i}. מקמהון הוסיף משתנים t_1,\cdots,t_n שמאפשרים להסתכל על G בעוד דרך: נסתכל על המכפלה \prod (t_i X_i)^{k_i}. מה שמעניין אותנו זה החלק בה שהוא פונקציה של \{t_i x_i \}, נגיד t_{1}^{3}x_{2}^{3} לא מתאים לנו. G מופיעה בדיוק בתור המקדם של \prod(t_i x_i)^{k_i}. מכאן נובע ש-\sum_{(k_1,\cdots, k_n)} \prod (t_i X_i)^{k_i} = \frac{1}{(1-t_1X_1) \cdots(1-t_nX_n)} היא כמעט הפונקציה היוצרת של G – המקדמים של \prod(t_i x_i)^{k_i} הם ערכי G, אבל יש עוד הרבה מקדמים מיותרים.

כעת נגדיר 2 מטריצות אלכסוניות – T,X שעל אלכסוניהן יהיו t_i, x_i. אנחנו רוצים להראות שהחלק של \prod \frac{1}{1-t_i X_i} שתלוי רק ב-\{ t_i x_i\} הוא \det(I-(TX)A)^{-1}. זה שקול לכך שהמנה \frac{\det(I-(TX)A)}{\prod (1-t_i X_i)} שווה ל-1 + גורמים שאינם פונקציות של \{t_i x_i \} בלבד.

נכתוב את הדטרמיננטה במונה בתור \det((I-TX)+T(X-XA)). החל מעכשיו נניח ש-n=3 למען הנוחות. ככה נראת הדטרמיננטה:

\det \begin{bmatrix} (1-t_{1}X_{1})+t_{1}(X_{1}-x_{1}a_{1,1}) & -t_{1}x_{1}a_{1,2} & -t_{1}x_{1}a_{1,3} \\ -t_{2}x_{2}a_{2,1} & (1-t_{2}X_{2})+t_{2}(X_{2}-x_{2}a_{2,2}) & -t_{2}x_{2}a_{2,3} \\ -t_{3}x_{3}a_{3,1} & -t_{3}x_{3}a_{3,2} & (1-t_{3}X_{3})+t_{3}(X_{3}-x_{3}a_{3,3}) \end{bmatrix}

נפתח את הדטרמיננטה הזו לפי הנוסחה הבאה, שנובעת מהמולטילינאריות של הדטרמיננטה: \det(D+A) = \sum_{I \subseteq \{ 1, 2, \cdots, n \}} \prod_{i \in I} d_i \det(A_{I^c}), כאשר D מטריצה אלכסונית עם d_1,\cdots, d_n על האלכסון, ו-A_{I} היא המטריצה המתקבלת מ-A ע"י לקיחת השורות והעמודות המאונדקסות ע"י I. נקבל:

\begin{aligned}  & & (1-t_{1}X_{1})(1-t_{1}X_{1})(1-t_{1}X_{1})\\  & + & (1-t_{1}X_{1})(1-t_{2}X_{2})\ensuremath{\det\begin{bmatrix}t_{3}(X_{3}-x_{3}a_{3,3})\end{bmatrix}}\\  & + & (1-t_{1}X_{1})(1-t_{2}X_{2})\ensuremath{\det\begin{bmatrix}t_{3}(X_{3}-x_{3}a_{3,3})\end{bmatrix}}\\  & + & (1-t_{1}X_{1})(1-t_{2}X_{2})\ensuremath{\det\begin{bmatrix}t_{3}(X_{3}-x_{3}a_{3,3})\end{bmatrix}}\\  & + & (1-t_{1}X_{1})\det\left[\begin{array}{cc}  t_{2}(X_{2}-x_{2}a_{2,2}) & -t_{2}x_{2}a_{2,3}\\  -t_{3}x_{3}a_{3,2} & t_{3}(X_{3}-x_{3}a_{3,3})  \end{array}\right]\\  & + & (1-t_{2}X_{2})\det\left[\begin{array}{cc}  t_{1}(X_{1}-x_{1}a_{1,1}) & -t_{1}x_{1}a_{1,3}\\  -t_{3}x_{3}a_{3,1} & t_{3}(X_{3}-x_{3}a_{3,3})  \end{array}\right]\\  & + & (1-t_{3}X_{3})\det\left[\begin{array}{cc}  t_{1}(X_{1}-x_{1}a_{1,1}) & -t_{1}x_{1}a_{1,2}\\  -t_{2}x_{2}a_{2,1} & t_{2}(X_{2}-x_{2}a_{2,2})  \end{array}\right]\\  & + & \det\begin{bmatrix}(t_{1}(X_{1}-x_{1}a_{1,1}) & -t_{1}x_{1}a_{1,2} & -t_{1}x_{1}a_{1,3}\\  -t_{2}x_{2}a_{2,1} & t_{2}(X_{2}-x_{2}a_{2,2}) & -t_{3}x_{2}a_{2,3}\\  -t_{3}x_{3}a_{3,1} & -t_{3}x_{3}a_{3,2} & t_{3}(X_{3}-x_{3}a_{3,3})  \end{bmatrix}  \end{aligned}

הגורם הראשון הופך ל-1 אחרי שנחלק במכפלה \prod (1-t_i X_i).

לגבי שאר הגורמים: לאחר שנחלק במכפלה \prod (1-t_i X_i) ונוציא את ה-t_i-ים החוצה, נקבל ביטויים מהצורה \frac{\prod_{i\in I} t_i \det((X-XA)_{I})}{\prod_{i \in I} (1-t_i X_i)}. ניקח ביטוי ספציפי שמתאים ל-I לא ריקה כלשהי. בגלל שה-t_i-ים היחידים שמופיעים הם \{ t_i \}_{i \in I}, כדי להראות שאף גורם בביטוי לא תלוי רק ב-\{ t_ix_i\} מספיק להראות שכשמחשבים את הדטרמיננטה \det((X-XA)_{I}), כל גורם יכיל איזשהו x_i עם i \notin I. כדי להראות זאת, נציב בדטרמיננטה \forall i \notin I: x_i = 0. אנחנו מגיעים לדטרמיננטה של מטריצה סינגולרית, כלומר מקבלים 0, כי כופלים את העמודה ה-i ב-x_i וסוכמים מקבלים 0.

דוגמא:

\begin{aligned} (1-t_{3}X_{3})\det\left[\begin{array}{cc}  t_{1}(X_{1}-x_{1}a_{1,1}) & -t_{1}x_{1}a_{1,2}\\  -t_{2}x_{2}a_{2,1} & t_{2}(X_{2}-x_{2}a_{2,2})  \end{array}\right]/\prod(1-t_{i}X_{i}) &= \\  \frac{t_{1}t_{2}}{(1-t_{1}X_{1})(1-t_{2}X_{2})} \det \left[\begin{array}{cc}  X_{1}-x_{1}a_{1,1} & -x_{1}a_{1,2}\\  -x_{2}a_{2,1} & X_{2}-x_{2}a_{2,2} \end{array}\right] & \end{aligned}

נציב x_3=0 והדטרמיננטה תתאפס:

\det\left[\begin{array}{cc}  -x_{2}a_{1,2} & -x_{1}a_{1,2}\\  -x_{2}a_{2,1} & x_{1}a_{2,1}  \end{array}\right]=0

הוכחה מאלגברה לינארית: ראשית, אזהרה: אני אניח פה הכרות מסויימת עם אלגברה מופשטת, ובלעדיה יהיה קשה לעקוב אחרי חלק גדול בהוכחה.

קודם כל, ננסח את המשפט בצורה קצת אחרת: \det(I-A)^{-1} =\sum_{(m_1,\cdots,m_n)} G(m_1,\cdots, m_n). כלומר במובן מסויים מספיק להוכיח את המשפט עבור t_1 = t_2 = \cdots = t_n=1. איך רואים את זה? אם נחליף בניסוח החדש את  A ב-TA, נקבל את הניסוח המקורי.

כעת, נשים לב שהמשפט ברור כשהמטריצה A אלכסונית. כשמחליפים את A במטריצה שדומה לה, הדטרמיננטה \det(I-A) לא משתנה כי I-P^{-1}AP=P^{-1}(I-A)P. מסתבר שגם הסכום \sum G(m_1,\cdots,m_n) לא משתנה, ועל כן המשפט נכון לכל מטריצה לכסינה. בגלל שכל מטריצה היא גבול של מטריצות לכסינות, המשפט נכון תמיד. (עם הטריק הזה אפשר להוכיח הרבה תוצאות, כמו משפט קיילי-המילטון.)

איך רואים שהסכום \sum G(m_1,\cdots,m_n) לא משתנה? בשביל זה נצטרך להסביר על כמה בניות מאלגברה לינארית, בניות שאינן תלויות בסיס ואפשר להביע בעזרתן את הסכום.

חזקה טנזורית, חזקה סימטרית וחזקה אנטי-סימטרית: יהי V מרחב וקטורי n-מימדי, לצורך העניין מעל המרוכבים, עם בסיס \{ e_i \}_{i=1}^{n}. החזקה הטנזורית ה-m-ית של V היא מרחק וקטורי חדש, ממימד n^m, שאיברי הבסיס שלו הם הביטויים הפורמליים e_{i_1} \otimes \cdots \otimes e_{i_m} כאשר 1 \le i_j \le n. הוא מסומן V^{\otimes m} = \underbrace{V\otimes V \otimes \cdots \otimes V}_{m\text{ times}}.

הדרך הסטנדרטית לבנות את המרחב הזה היא לקחת בהתחלה את כל הקומבינציות הלינאריות מהצורה v_1 \otimes \cdots \otimes v_m כאשר v_i \in V. השלב הבא הוא להתייחס ל-v_1 \otimes \cdots \otimes v_m בתור פונקציה m-לינארית, כלומר להגדיר את השיוונות הבאים:

(cv_1) \otimes v_2 \otimes \cdots = v_1 \otimes (cv_2) \otimes \cdots = \cdots = v_1 \otimes v_2 \otimes \cdots \otimes (cv_m) = c (v_1 \otimes v_2 \otimes \cdots )

v_1 \otimes \cdots \otimes (v_i + u_i) \otimes v_{i+1} \otimes \cdots = v_1 \otimes \cdots \otimes v_i \otimes v_{i+1} \otimes \cdots \otimes v_m + v_1 \otimes \cdots \otimes u_i \otimes v_{i+1} \otimes \cdots \otimes v_m

וככה מקבלים שכל איבר הוא קומבינציה של אחד מאיברי הבסיס שהזכרנו. בנייה זו מאוד חשובה ומאפשרת לעשות לינאריזציה להרבה בעיות, לדוגמא: פונקציה בי-לינארית על V^{2} הופכת להיות פונקציה לינארית על V^{\otimes 2}.

אם יש לי אופרטור A שפועל על V, אפשר להגדיר אופרטור A^{\otimes m} שפועל על V^{\otimes m} באופן הבא:

A(v_1 \otimes v_2 \otimes \cdots ) = (Av_1) \otimes (Av_2) \otimes \cdots

ואפשר לבנות מתוך המטריצה של A בבסיס e_i את המטריצה של A^{\otimes m} בבסיס e_{i_1} \otimes e_{i_2} \otimes \cdots. כמו שהדטרמיננטה והטרייס הן אינווריאנטות של A, כך גם הדטרמיננטה והטרייס של A^{\otimes m} (שלא יוצאים מאוד מעניינים – \text{Trace}(A^{\otimes m}) = (\text{Trace}(A))^m, \det(A^{\otimes m}) = \det(A)^{m}).

החזקה הסימטרית והחזקה האנטי-סימטרית מתקבלות מהחזקה הטנזורית ע"י הוספת יחסים נוספים בין האיברים.

החזקה הסימטרית מתקבלת ע"י כך שנדרוש שהפונקציות v_1 \otimes \cdots \otimes v_m יהיו סימטריות, כלומר נגדיר שיוויונים מהצורה:

v_1 \otimes \cdots \otimes v_m = v_{\sigma(1)} \otimes \cdots \otimes v_{\sigma(m)}

עבור פרמוטציות \sigma \in S_m (מספיק לדרוש זאת עבור חילופים.) הבסיס הופך להיות:

e_{i_1} \otimes \cdots \otimes e_{i_m}, 1 \le i_1 \le i_2 \le \cdots \le i_m \le n

ומימד המרחב נהיה \binom{m+n-1}{m}. החזקה הסימטרית מסומנת S^{n}(V). אפשר להגדיר את האופרטור S^{n}(A) שפועל על המרחב החדש:

S^{n}(A)(v_1 \otimes v_2 \otimes \cdots \otimes v_m) = (Av_1) \otimes \cdots \otimes (Av_m)

החזקה האנטי-סימטרית מוגדרת ע"י יחסים אנטי-סימטריים:

v_1 \otimes \cdots \otimes v_m = (-1)^{\text{sign}(\sigma)} v_{\sigma(1)} \otimes \cdots \otimes v_{\sigma(m)}

 כלומר, חילוף של 2 וקטורים גורם להיפוך הסימן. בפרט, אם אותו וקטור מופיע פעמיים, הביטוי מתאפס כי אם נבחר את הפרמוטציה המחליפה בין 2 הוקטורים הראשונים, נקבל:

e_1 \otimes e_1 \otimes e_3 = -e_1 \otimes e_1 \otimes o_3 \implies e_1 \otimes e_1 \otimes e_3 = 0

לכן הפעם הבסיס קטן יותר:

e_{i_1} \otimes \cdots \otimes e_{i_m}, 1 \le i_1 < i_2 < \cdots <i_m \le n

ומימד המרחב \binom{n}{m}. הוא מסומן \Lambda^{n}(V), ושוב אפשר להגדיר באופן טבעי את האופרטור המושרה \Lambda^{n}(A).

כמו במקרה של החזקה הטנזורית, הדטרמיננטה והטרייס של S^{n}(A), \Lambda^{n}(A) לא תלויות בבסיס – פשוט כי את כל הבניות שעשינו אפשר לעשות ללא תלות בבסיס.

אפשר לוודא את השיוויונות הבאים, לדוגמא ע"י שימוש בבסיסים שבנינו:

\det(I-A) = \sum_{i=0}^{n} (-1)^{i} \text{Trace} (\Lambda^{i} (A) )

\sum_{\sum m_i =r} G(m_1, \cdots, m_n) = \text{Trace}( S^{r}(A) )

ומשפט מקמהון הופך לשיוויון הבא:

(\sum_{k} \text{Trace}(S^{k}(A)) (\sum_{r} (-1)^{r} \text{Trace}(\Lambda^{r}(A))) = 1

שיוויון מקסים זה מוכר בפיזיקה בתור "Boson-Fermion Correspondence". דרך שכיחה לכתוב אותו היא:

\frac{1}{\sum_{r} (-1)^{r} \text{Trace}(\Lambda^{r}(A)) t^r} = \sum_{k} \text{Trace}(S^{k}(A)) t^{k}

השוואת ביטויים מאותה מעלה הופכת את השיוויון הזה לאוסף שיוויונות פולינומיאליים:

\forall m: \sum_{r+k = m} (-1)^{r} \text{Trace}(\Lambda^{r}(A)) \text{Trace}(S^{k}(A)) = \delta_{m,0}

כאשר המטריצות אלכסוניות, למעשה כבר וידאנו שיוויון זה (בתרגיל 21 אני מפציר בכם לתת הוכחה קומבינטורית). היופי בשיוויון זה הוא שהוא באמת מראה שאין תלות בבחירת הבסיס ולכן השיוויון נכון למטריצות לכסינות ולכן לכל המטריצות.

הוכחה מהיפוך לגראנז': היפוך לגראנז' הוא משפט חזק ושימושי (שאפשר להקדיש לו פוסט שלם). הוא מאפשר להפוך טורי חזקות – אם לדוגמא אני יודע להביע את y כטור חזקות ב-x (נגיד y=xe^x), היפוך לגראנז' מאפשר לי להביע את x באמצעות y במובן הבא: הוא נותן לי נוסחה מפורשת למקדמי טור החזקות של x כפונקציה של y. שימושי לאללה בפתרון משוואות פונקציונליות שצצות בקומבינטוריקה (דוגמאות בהמשך).

למשפט יש הרבה ניסוחים, אלגנטיים ו/או סימטריים יותר או פחות. נשתמש בניסוח הבא:

x=\frac{y}{f(y)}, f(0) \neq 0 \implies [x^m] y =\frac{1}{m} [y^{m-1}]f^{m} = [y^m] y(\frac{y}{f(y)})' f^{m+1}

שאפשר להכליל באופן הבא:

x=\frac{y}{f(y)}, f(0) \neq 0 \implies [x^m] g(y) =\frac{1}{m} [y^{m-1}]g'(y) f^{m} = [y^m] g(y)(\frac{y}{f(y)})' f^{m+1}

ניתן שתי דוגמאות סטנדרטיות. אם נסמן ב-C את הפונקציה היוצרת של מספרי קטלן, היא מקיימת את המשוואה C=1+xC^2. המשפט דורש פונקציות שמתאפסות באפס (כלומר "מתחלקות" ב-x), אז נסמן B=C-1, פונקציה שמתאפסת באפס ומקיימת x = \frac{B}{(B+1)^2}. היפוך לגראנז' מאפשר להביע את מקדמי B בעזרת הפונקציה במכנה, (1+y)^2:

\forall m > 0: [x^m] C(x) = [x^m] B(x) = \frac{1}{m} [y^{m-1}](1+y)^{2m} = \frac{1}{m}\binom{2m}{m-1}

עוד דוגמא: נסמן ב-T את הפונקציה היוצרת האקספוננציאלית של מספרים העצים הפורשים של K_n (הגרף השלם עם n קודקודים) עם קודקוד מסומן, כלומר: זוג סדור של עץ פורש וקודקוד שלו. ברור שכדי לקבל את מספרים העצים הפורשים צריך פשוט לחלק ב-n. הפונקציה היוצרת מקיימת את המשוואה x=\frac{T}{e^T}, ולכן אפשר להשתמש בהיפוך לגראנז':

[x^m] T(x) = \frac{1}{m} [y^{m-1}] e^{my} = \frac{m^{m-1}}{m(m-1)!} = \frac{m^{m-1}}{m!}

ומקבלים שמספר העצים הפורשים של K_n הוא n^{n-2} (משפט קיילי).

נחזור למשפט מקמהון. אם נבחר בהיפוך לגראנז' g(y)=(1-y\frac{f'(y)}{f(y)})^{-1}, נקבל:

[x^m] g(y) = [y^m]f^m

כלומר g(y) היא הפונקציה היוצרת של המקדם ה-m-י של f-י. במשפט מקמהון אנחנו רוצים לחשב את הפונקציה היוצרת של המקדם של \prod x_i^{k_i} ב-\prod f_i^{k_i} כאשר f_i = \sum a_{i,j} x_j. זו ממש אותה סיטואציה! (אם נבחר f(y)=1+cy נקבל את מקמהון במשתנה אחד) לא נתתי את הניסוח של היפוך לגראנז' לכמה משתנים (כי הוא קצת סבוך), אבל אני אתן את ההוכחה עבור המקרה הפרטי של מקמהון (את ההוכחה אפשר להכליל להוכחה להיפוך לגראנז'). נסמן Y_i = 1+f_i (כי f_i מתאפסות בראשית). המקדם של \prod x_i^{m_i} ב-\prod f_i^{m_i} שווה לאותו מקדם ב-\prod Y_i^{m_i} ששווה ל:

\frac{1}{(2\pi i)^n} \int \cdots \int \frac{\prod Y_i^{m_i}}{\prod x_i^{m_i + 1}} dx_1 \cdots dx_n

כאשר האינטגרל ה-i-י הוא על פני מעגל קטן מספיק עם מרכז ב-0. נעשה עכשיו חילוף משתנים w_i = \frac{x_i}{Y_i} ונקבל את האינטגרל:

\frac{1}{(2\pi i)^n} \int \cdots \int \frac{\det D^{-1}}{(\prod Y_i) (\prod w_i^{m_i + 1})} dw_1 \cdots dw_n

כאשר D היא היעקוביאן של \{w_i\} לפי \{ x_j \}, שיוצא: D_{i,j} = \frac{\delta_{i,j} - w_i a_{i,j}}{Y_i}. אם מכפילים את השורה ה-i ב-Y_i מקבלים את I-WA, ולכן האינטגרל הופך ל:

\frac{1}{(2\pi i)^n} \int \cdots \int \frac{\det (I-WA)^{-1}}{\prod w_i^{m_i + 1}} dw_1 \cdots dw_n

 וזה המקדם של \prod w_i^{m_i} ב-\det(I-WA)^{-1}, כמו שרצינו להראות:

[w_1^{m_1} \cdots w_n^{m_n}] \det(I-WA)^{-1} = [x_1^{m_1} \cdots x_n^{m_n}]\prod Y_i^{m_i} = [x_1^{m_1} \cdots x_n^{m_n}]\prod f_i^{m_i}

\blacksquare

ההוכחה הקומבינטורית: נתחיל לבנות את המושגים שישמשו אותנו בהוכחה הקומבינטורית – תתאזרו בסבלנות. מדובר בהוכחה שמזכירה את ההוכחה הקומבינטורית של Foata מהחלק הקודם. יתכן שהיא מעט מסורבלת, אבל אני מקווה שהאינבולוציה תהיה מובנת.

גרפים מכוונים ממושקלים: נחקור גרפים מכוונים. הקודקודים יהיו \{1,2,\cdots, n\}, ויהיה לנו אוסף משקולות w(i,j) לכל הצלעות i \to j האפשריות.

גרפי פרמוטציה: משקל של מעגל מכוון a_1 a_2 a_3 \cdots a_k a_1 יוגדר כמינוס מכפלת משקלי הצלעות: -w(a_1,a_2)w(a_2,a_3)\cdots w(a_k, a_1).

עבור פרמוטציה \pi על קבוצה A \subseteq \{1,2,\cdots,n\} אפשר לבנות גרף מכוון על \{1,2,\cdots ,n\} באופן הטבעי הבא: הצלעות יהיו i \to \pi(i) עבור i \in A. הגרף יסומן D(\pi) ומשקלו יהיה מכפלת המשקלים של מעגלי הגרף (שמתאימים למעגלי הפרמוטציה):

w(D(\pi)) = \prod_{\text{cycle}} w(\text{cycle}) = (-1)^{\#\text{cycles}} \prod_{i\in A}w(i,\pi(a))

נסמן ב-\mathbb{H} את אוסף גרפי הפרמוטציה. משקל אוסף זה יוגדר להיות סכום המשקלים של איבריו. נסמן ב-W את המטריצה שאיבריה הם המשקולות w(i,j). השלב הבא שלנו יהיה לוודא את הזהות הבאה, שמסבירה את הקשר למשפט מקמהון:

w(\mathbb{H}) =\sum_{h \in \mathbb{H}} w(h) = \det(I-W)

פירוש קומבינטורי לדטרמיננטה: תהי A מטריצה n \times n, שאיבריה a_{i,j} הם בדיוק המשקולות w(i,j). מהנוסחה המפורשת לדטרמיננטה מקבלים:

\det(-A) = \sum_{\pi \in S_n} w(D(\pi))

(השתמשנו בכך שסימן של פרמוטציה על n איברים ועם k מעגלים הוא (-1)^{n+k}.)

בנוסף, אם פותחים סוגריים בפולינום p(x) = \det(x I-A), מקבלים שהמקדם של x^{n-i} הוא \sum_{B \text{ is a principal minor of -A of size } i\times i} \det(B). אם נציב x=1 נקבל את השיוויון w(\mathbb{H}) = \det(I-W).

גרפי איחוד מעגלים: נסמן ב-\mathbb{D} את אוסף הגרפים המכוונים שמורכבים מאיחוד מעגלים (לאו דווקא זרים), כלומר לכל קודקוד יש דרגת יציאה השווה לדרגת הכניסה. בנוסף, נדרוש לכל קודקוד יהיה יחס סדר על הצלעות היוצאות מתוכו (נפרט ונדגים עוד רגע).

בגרפים אלו מטריצת המשקולות שנגדיר היא W=AT כאשר A מטריצה של משתנים a_{i,j} ו-T מטריצה אלכסונית שבאלכסונה גם כן משתנים, t_1, \cdots, t_n.

נשכלל קצת את המשקולות: נחליף את המשקל של הצלע ה-k-י שיוצאת מקודקוד i ב-a_{i,j}^{k} t_j במקום סתם a_{i,j}t_j. (ה-k הוא סימון, כלומר a_{i,j}^{k} הוא משתנה חדש.)

הנחת החילופיות שלנו תהיה זו בינתיים: הכל מתחלף עם הכל, חוץ מה-t_j שלא מתחלפים בינם לבין עצמם. (בשלב כלשהו נרשה להם להתחלף.)

משקל של גרף באוסף יהיה מכפלת המשקלים של צלעותיו. בגלל שסדר הכפל חשוב, אפרט מה הסדר: נלך קודם על צלעות שיוצאות מהקודקוד 1, אח"כ אלו שיוצאות מהקודקוד 2, וכן הלאה. עבור צלעות שיוצאות מאותו קודקוד יש לנו כבר יחס סדר.

משקל האוסף כולו יהיה סכום המשקלים של הגרפים באוסף: w(\mathbb{D}) = \sum_{d\in D} w(d).

הבחנה: המשקל של גרף במשפחה הזו מזהה את הגרף בצורה חד-חד-ערכית. למעשה, מספיק להסתכל במשקל על המשתנים t_i והסדר ביניהם. ניתן דוגמא. נניח שמשקל הגרף d הוא:

a_{1,1}^{1}t_{1} a_{1,3}^{2}t_{3} a_{1,3}^{3}t_{3}a_{2,2}^{1}t_{2}a_{3,1}^{1}t_{1}a_{3,1}^{2}t_{1}a_{3,3}^{3}t_{3}

בעזרת החילופיות, משקל זה הוא בעצם a_{1,1}^{1} a_{1,3}^{2} a_{1,3}^{3}a_{2,2}^{1}a_{3,1}^{1}a_{3,1}^{2}a_{3,3}^{3}t_{1}t_{3}^{2}t_{2}t_{1}^{2}t_{3}. אני טוען שהחלק של ה-t-ים מספיק כדי לשחזר את d. נראה איך אנחנו בונים את d מתוך t_{1}t_{3}^{2}t_{2}t_{1}^{2}t_{3}. ראשית, כמו ה-t_i-ים מלמדת אותנו מה דרגות הכניסה והיציאה: קודקוד 1 בעל דרגת כניסה/יציאה 3, קודקוד 2 בעל דרגה 1 וקודקוד 3 בעל דרגה 3. לכן, 3 המשתנים הראשונים מתאימים לצלעות 1 \to i, אחריהם צלע 2 \to j ושלוש המשתנים האחרונים מתאימים לצלעות 3 \to k. כלומר t_{1}t_{3}^{2} מלמד אותנו שהצלעות שיוצאות מקודקוד 1 הן 1\to 1, 1\to 3, 1 \to 3, וכן הלאה. שימו לב ששחזור זה נותן גם את יחס הסדר על הצלעות.

במשפט מקמהון אנחנו מעוניינים במקדם של t_{1}^{m_1} \cdots t_{n}^{m_n} במכפלה (a_{1,1}t_1 + \cdots + a_{1,n}t_n)^{m_1}(a_{2,1}t_1 + \cdots + a_{n,2}t_2)^{m_2}\cdots(a_{n,1}t_1 + a_{n,2}t_2 + \cdots + a_{n,n}t_n)^{m_n}, כאשר ה-t_i-ים מתחלפים. נסמנו ב-B(m_1,\cdots,m_n).

כדי להבין מכפלה זו, נסתכל על המכפלה המסומנת, בה כל גורם (a_{i,1}t_1 + \cdots + a_{i,n}t_n)^{m_i} נכתוב בתור (a_{i,1}^{1} t_1 + \cdots + a_{i,n}^{1}t_n)\cdots (a_{i,1}^{m_i} t_1 + \cdots + a_{i,n}^{m_i}t_n). כשפותחים סוגריים, מקבלים משקלים של כל מיני גרפים מכוונים בהם דרגת היציאה של קודקוד i היא m_i. אם מסתכלים רק על הגורמים בהם כמות ה-t_i-ים היא m_i (לכל i), מקבלים משקלים חוקיים של גרפים מכוונים בהם דרגת הכניסה של הקודקוד i שווה לדרגת היציאה שווה ל-m_i, ואלו גרפים שנמצאים באוסף \mathbb{D}.

בעקבות ההבנה את המקדם הנחוץ, נסתכל על w(\mathbb{D}) בתור פונקציה יוצרת של המקדמים הללו – אם נוריד את הסימון העילי ונניח חילופיות ה-t_i-ים, אפשר לראות ש:

w(\mathbb{D}) = \sum_{d \in \mathbb{D}} w(d) = \sum_{(m_1,\cdots,m_n)} B(m_1,\cdots, m_n) y_1^{m_1} \cdots y_n^{m_n}

לפני שממשיכים להוכחה, ודאו שאתם מבינים הכל עד כה, בעיקר את האוספים \mathbb{D},\mathbb{H}.

ההוכחה: אנחנו מוכנים. המשפט גורס כי הפונקציה היוצרת של B(m_1, \cdots, m_n) היא \det(I - AT)^{-1}. כבר ראינו ייצוג אחד לפונקציה היוצרת והוא w(\mathbb{D}). גם לדטרמיננטה \det(I-AT) ראינו ייצוג קומבינטורי והוא w(\mathbb{H}). אנחנו בעצם נדרשים להוכיח:

w(\mathbb{D}) w(\mathbb{H}) = \sum_{d\in \mathbb{D}, h\in \mathbb{H}} w(d)w(h) = 1

נציג אינבולוציה הופכת סימן על הזוגות (d,h) \in \mathbb{D} \times \mathbb{H}. נקודת השבת היחידה שלה תהיה הזוג של הגרף הריק ללא צלעות, (\varnothing, \varnothing), שמשקלו 1 והוא מסביר את אגף ימין.

האינבולוציה היא כזו: נניח שהזוג הוא (d,h). נזכור שהקודקודים ממוספרים. נמצא את הקודקוד הכי קטן שיוצאת ממנו צלע באחד הגרפים d,h. נתחיל לטייל, החל מקודקוד זה, בגרף D. בטיול זה, תמיד נבחר בצלע המקסימלית (נזכר שיש יחס סדר על הצלעות). אנחנו עוצרים כשקורה אחד משני המקרים הבאים:

1. אנחנו מגיעים לקודקוד שכבר היינו בו וכך מצאנו מעגל ב-d. נסמן מעגל זה ב-\gamma.

2. אנחנו מגיעים לקודקוד שיש לו דרגת יציאה חיובית ב-h. קודקוד זה חייב להימצא על מעגל יחיד ב-h, נסמנו \delta.

ראשית, נשים לב ששני המקרים לא יכולים לקרות בו"ז. שנית, נשים לב שאחד המקרים חייב לקרות. (השתכנעו בכך!)

במקרה הראשון, נעביר את המעגל \gamma לגרף h, וכך נקבל זוג (d',h') שגם מופיע בסכום.

במקרה השני, נעביר את המעגל \delta לגרף d. בגלל שב-d יש יחס סדר על הצלעות, צריך להסביר גם מה הסדר של הצלעות החדשות שהכנסנו אליו. אם הכנסנו את הצלע i \to j, היא תהיה 'גדולה' מכל הצלעות האחרות שיוצאות מקודקוד i.

בשני המקרים, לזוג החדש (d',h') משקל עם סימן הפוך (כי ב-w(h) יש את הגורם (-1)^{\# \text{cycles}}). אשאיר לכם לוודא שההתאמה (d,h)\to(d',h') היא אינבולוציה. \blacksquare

דוגמא: נניח שצלעות d הן a_{1,5}^{1}a_{2,3}^{1}a_{3,2}^{1}a_{3,5}^{2}a_{3,1}^{3}a_{5,3}^{1}a_{5,3}^{2} וצלעות h הן a_{2,4}a_{3,3}a_{4,6}a_{6,2}. נתחיל את הטיול בקודקוד 1. הצעד הראשון יהיה על הצלע a_{1,5}^{2} והשני על הצלע a_{5,3}^{2}. ל-3 יש דרגת יציאה חיובית ב-h כי הוא נמצא על הלולאה 3 \to 3. נעביר לולאה זו מ-h ל-d בתור a_{3,3}^{4}.

אם נפעיל את האלגוריתם הזה על הזוג החדש (d',h'), נגיע שוב לקודקוד 3. הפעם ב-h' תהיה לו דרגת יציאה אפס (הורדנו את הלולאה משם), ולכן נמשיך לצעוד על הלולאה a_{3,3}^{4} ב-d', ונגיע למקרה הראשון, שמחייב אותנו להחזיר את הלולאה ל-h'.

הערה לחדי האבחנה: בניסוח המקורי כתבנו \det(I - TA), ובהוכחה דווקא כפלנו ב-T מהצד השני: \det(I-AT). זה לא משנה, כי אם A הפיכה אז: \det(I-TA) = \det(A(I - TA)A^{-1}) = \det(I-AT). כש-A לא הפיכה, זה נכון כי אפשר לכתוב אותה כגבול של מטריצות הפיכות. סילבסטר הכליל תוצאה זו במשפט שלו.

הערה אחרונה: אפשר לנסח את ההוכחה הזו בצורה קצת אחרת, ולהסתכל על משפט מקמהון כסוג של היפוך מביוס על פרמוטציות. לא אפרט על זה כן, תוכלו לקרוא על כך בתרגילים 19 ו-20 בעמוד 33 בספר The Art of Computer Programming, Vol III של Knuth.

תרגיל 19 (פונקציות סימטריות): יהיו \{ x_i\}_{i=1}^{n} משתנים (או מספרים). יש 2 סוגים של פולינומים סימטריים על n איברים:

  •  הפולינום האלמנטרים e_i שמוגדרים בתור סכום כל המכפלות של i איברים שונים. לדוגמא, e_2 = \sum_{i<j} x_i x_j.
  • הפולינומים המלאים s_i שמוגדרים בתור סכום כל המונומים ממעלה i במשתנים \{ x_i \}_{i=1}^{n}. לדוגמא, s_2 = \sum_{i<j} x_i x_j + \sum_{i} x_{i}^{2}.

הראו את השיוויון הבא: \sum_{i=0}^{k} (-1)^{i} e_i s_{k-i} = \delta_{k,0}.

תרגיל 20: נגדיר את הפרמננטה של מטריצה להיות דטרמיננטה ללא הסימנים המתחלפים: \text{Per}(A) = \sum_{\pi \in S_n} \prod_{i=1}^{n} a_{i,\pi(i)}. עבור I \subseteq \{1,2,\cdots, n\} נסמן ב-A_{I} את המטריצה ה-|I| \times |I| המתקבלת מ-A ע"י לקיחת השורות והעמודות המאונדקסות ע"י I. הוכיחו כי:

\sum_{I \subseteq \{1,2,\cdots, n \} } (-1)^{|I|} \det(A_{I})\text{per}(A_{I^c}) = 0

(פרמננטה ודטרמיננטה של מטריצות 1 על 1 מוגדרות להיות 1.)

תרגיל 21: הוכיחו כי \sum_{k} \binom{k}{k-m,k-n,n+m-k} (1-)^{k+m+n} = 1.

תרגיל 22 (עוד שימושים באלגברה לינארית):

i. ה-Pfaffian: תהי A מטריצה n \times n אנטי-סימטרית, כלומר A^{T} = -A. כש-n אי-זוגי, בהכרח \det(A) = 0. אבל כש-n זוגי, \det(A) היא ריבוע של פולינום באיברי המטריצה. פולינום זה נקרא ה-Pfaffian. לדוגמא, במקרה הפשוט של 2 על 2, מקבלים a_{1,2}^{2}. במקרה של n=4 מקבלים (a_{1,2}a_{3,4}-a_{1,3}a_{2,4}+a_{1,4}a_{2,3})^{2}. הראו שאכן תמיד מקבלים ריבוע של פולינום.

ii. הלמה של Lindström–Gessel–Viennot: יהי G גרף מכוון ללא מעגלים, לאו דווקא סופי. לדוגמא, הגרף שקודקודיו הם איברי השריג \mathbb{Z}^{2} וצלעותיו הן \{ (i,j) \to (i,j+1), (i,j) \to (i+1,j) | i,j\in \mathbb{Z} \} (צעדים ימינה ולמעלה). נבחר n קודקודים שיקראו נקודות התחלה: a_1, \cdots a_n, ועוד n קודקודים שיקראו נקודות סיום: b_1, \cdots, b_n.

בנוסף, נניח שצלעות הגרף ממושקלות ע"י פונקציה w: E \to \mathbb{C}. למסלול מכוון בגרף ניתן בתור משקל את מכפלת משקולות צלעותיו: w(v_1 v_2 \cdots v_n) = \prod w(v_i v_{i+1}).

לכל זוג קודקודים a,b נסמן ב-e(a,b) את סכום המשקולות של המסלולים המכוונים מ-a ל-b. נגדיר את המטריצה הבאה:

M_{i,j} = e(a_i, b_j), 1\le i,j\le n

הלמה נותנת פירוש קומבינטורי לדטרמיננטה של M: נסתכל על n-יות של מסלולים (P_1, \cdots, P_n) שלא נחתכים בקודקודים. נדרוש שהמסלול P_i מתחיל בנקודת ההתחלה a_i ומסתיים באיזושהי נקודת סיום b_{f(i)}. בגלל שהמסלולים לא נחתכים, f היא פרמוטציה על \{1, 2,\cdots, n\}, אותה נסמן ב-\pi(P). אז הדטרמיננטה היא –

\sum_{(P_1,\cdots,P_n)} \text{sign}(\pi(P)) \prod_{i=1}^{n} w(P_i)

הוכיחו את הלמה. יש לה אינספור שימושים בקומבינטוריקה ובתורת ההצגות של החבורה הסימטרית.

iii. הוכיחו שדטרמיננטה היא פונקציה כפלית.

תרגיל 23: \sum_{i+j+k=n} \binom{i+j}{i} \binom{j+k}{j} \binom{k+i}{k} = \sum_{l=0}^{n} \binom{2l}{l}.

לקריאה נוספת:

A Course in Enumeration  של Martin Aigner – ספר מוצלח ודיי חדש במתמטיקה דיסקרטית.

Advanced Combinatorics של Louis Comtet – עוד ספר מעניין במתמטיקה דיסקרטית.

Problèmes combinatoires de commutation et réarrangements של Foata ו-Cartier – ספר קומבינטוריקה בצרפתית. מה שהבנתי אהבתי, לצערי לא הבנתי מספיק. חלקים מסויימים מופיעים גם בספרים אחרים, לדוגמא Combinatorics on Words של M. Lothaire.

מקווה שנהנתם,

אופיר

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה חפירה, כללי, קומבינטוריקה. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

2 תגובות על על שלוש זהויות, אינבולוציות הופכות סימן ומשפט מקמהון

  1. טל הגיב:

    יש לך טעות במקרה s=1. איקס מעל אפס שווה 1 (ולא אפס כמו שכתבת)

    (תודה, תוקן. -אופיר)

  2. פינגבאק: אלגוריתמים להוכחת זהויות קומבינטוריות | One and One

להשאיר תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s