הוכחתו של Joyal לנוסחת Cayley
1. קישור ערים ע”י כבישים
נניח שאנחנו מהנדסים הנדרשים לתכנן כבישים שיקשרו בין \({n}\) ערים. בשפה מתמטית, הלקוחה מן התחום שנקרא תורת הגרפים, נתונים לנו \({n}\) קודקודים (המייצגים ערים), והם מסומנים ע”י המספרים \({1,2,\ldots,n}\). אנחנו צריכים להחליט אילו זוגות של קודקודים יחוברו ע”י צלעות (המייצגות כביש ישיר בין שתי ערים). המטרה היא להבטיח שיהיה אפשר להגיע מכל עיר לכל עיר אחרת, לאו דווקא ע”י כביש ישיר ביניהן. בשפת תורת הגרפים, מדובר בגרף קשיר על \({n}\) הקודקודים. אפשר כמובן לחבר כל זוג קודקודים ע”י צלע, אבל זה מאוד לא חסכוני \({-}\) מספר הכבישים שיידרש הוא \({{n \choose 2} = \frac{n(n-1)}{2}}\).
מהו המספר המינימלי של כבישים המקשרים בין \({n}\) ערים? קל להיווכח כי מספר זה הוא \({n-1}\). באיור 1 אנחנו מציגים כמה אפשרויות לקשר בין \({5}\) ערים ע”י \({4}\) כבישים:
גרף קשיר על \({n}\) קודקודים בעל \({n-1}\) צלעות נקרא עץ. כאמור, זה המספר המינימלי של צלעות המאפשר קשירות. בהינתן עץ, לכל שני קודקודים יש דרך אחת ויחידה להגיע מהאחד לשני.
2. עצים מתויגים
בכמה אופנים שונים ניתן לקשר בין \({n}\) ערים ע”י \({n-1}\) כבישים? לפני שעונים על השאלה, חשוב להחליט אם מייחסים חשיבות לזהותן של הערים. אם כן, אנחנו מדברים על עצים מתויגים (כלומר, לכל קודקוד יש תג המציין את שמו). אם לא, אנחנו מדברים על עצים לא מתויגים.
כדי להבהיר נקודה זו, נתבונן שוב באיור 1. העץ המופיע ב-(א) יכול להופיע ב-\({5}\) התגלמויות שונות (בציור קודקוד \({1}\) הוא זה שמחובר לכל קודקוד אחר; אבל אפשר לבחור את קודקוד \({2}\) להיות זה שמחובר לכל האחרים, או את קודקוד \({3}\), וכו’). כאשר מדובר בעצים מתויגים, אנחנו סופרים את \({5}\) האפשרויות כשונות זו מזו. כאשר אנו מתעניינים בעצים לא מתויגים, הן נספרות כאפשרות אחת. באופן דומה (עם חשבון מעט יותר מורכב), אפשר להיווכח שקיימים \({60}\) עצים מתויגים שהם התגלמויות שונות של איור 1(ב), וכן \({60}\) עצים מתויגים שהם בדמותו של איור 1(ג). בסך הכול, יש רק \({3}\) עצים לא מתויגים על \({5}\) קודקודים, אבל \({5+60+60=125}\) עצים מתויגים על \({5}\) קודקודים.
נסמן ב- \({u_n}\) את מספר העצים הלא מתויגים על \({n}\) קודקודים, וב- \({a_n}\) את מספר העצים המתויגים על \({n}\) קודקודים. הקוראים יוכלו להיווכח בעצמם בנכונות הערכים בטבלה הבאה עבור \({n \le 5}\):
| \(a_n\) | \(u_n\) | \(n\) |
|---|---|---|
| \(1\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(2\) |
| \(3\) | \(1\) | \(3\) |
| \(16\) | \(2\) | \(4\) |
| \(125\) | \(3\) | \(5\) |
מעיון בטבלה, עולה תבנית להתנהגות המספרים \({a_n}\). שימו לב שכל ערך של \({a_n}\) ניתן לכתיבה כחזקה:
\(\displaystyle a_1=1=1^{-1}, \quad a_2=1=2^0, \quad a_3=3=3^1, \quad a_4=16=4^2, \quad a_5=125=5^3 \)
תבנית זו נראית פשוטה באופן מפתיע, בפרט בהתחשב באופן שבו הגענו למספרים (למשל, \({125=5+60+60}\)). היא מובילה אותנו לנחש נוסחה כללית עבור \({a_n}\):
\(\displaystyle a_n = n^{n-2} \)
מסתבר שנוסחה זו אכן נכונה, והיא קרויה נוסחת קיילי על שמו של \({\textrm{Arthur Cayley}}\), שכתב עליה במאמר קצר בשנת \({1889}\). התוצאה המקורית היא של \({\textrm{Carl Wilhelm Borchardt}}\), שגילה אותה ב-\({1860}\). זו נוסחה יפה במיוחד בזכות פשטותה והיותה בלתי צפויה: נדיר בקומבינטוריקה שמקבלים נוסחה כה פשוטה לבעיה לא טריביאלית, ואם בדקתם את ערכי \({a_n}\) בטבלה בעצמכם בוודאי תסכימו שהנוסחה בלתי צפויה\(^1\). לנוסחת קיילי ידועות הוכחות רבות, ואנו נציג כאן אחת אלגנטית מאוד שניתנה ע”י \({\textrm{Andr’e Joyal}}\) ב-\({1980}\). אבל לפני כן, נידרש לנושא אחר, ונדון בהצגות של תמורות.
3. תמורות ודרכים להציגן
במילים פשוטות, תמורה של קבוצה בת \({n}\) איברים היא סדרה שבה מופיעים \({n}\) האיברים בסדר כלשהו. יש כמה דרכים מקובלות להציג תמורות.
1.3 כתיבה בשורה אחת
זו כנראה הצורה המוכרת ביותר להציג תמורה. בשורה אחת, תמורה נכתבת ע”י מניית האיברים לפי סדר הופעתם משמאל לימין. למשל, כשמדובר בקבוצה \({\{1,2,3,4,5,6\}}\), נכתוב
\(\displaystyle 341652 \)
כאשר נתכוון לתמורה שבה \({3}\) מופיע ראשון, \({4}\) שני, \({1}\) שלישי, \({6}\) רביעי, \({5}\) חמישי, \({2}\) אחרון.
2.3 כתיבה בשתי שורות ופירוק למעגלים
במתמטיקה נהוג לחשוב על תמורה כפונקציה חד-חד-ערכית מקבוצה על עצמה. למשל, בתמורה שנכתבת \({341652}\) בכתיב של שורה אחת, הקבוצה היא \({\{1,2,3,4,5,6\}}\) והפונקציה מתאימה למקום \({1}\) את האיבר \({3}\), למקום \({2}\) את האיבר \({4}\), וכן הלאה. החד-חד-ערכיות של ההתאמה מבטיחה היעדר חזרות בסדרה. הכתיבה בשתי שורות ממחישה את ההתאמה. בשורה העליונה כותבים את האיברים בסדר המקורי, ובשורה השנייה בסדר שנקבע ע”י התמורה:
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 1 & 6 & 5 & 2 \end{pmatrix} \)
המשמעות היא \({1}\) עובר ל- \({3}\), \({2}\) עובר ל- \({4}\), \({3}\) עובר ל- \({1}\), וכן הלאה.
היתרון של כתיבה בשתי שורות הוא שהיא מקלה עלינו לעקוב אחר הקורה לאיבר כאשר מפעילים את הפונקציה שוב ושוב. בדוגמה הנ”ל, \({1}\) עובר ל- \({3}\), ואילו \({3}\) עובר ל- \({1}\), מה שמחזיר אותנו לנקודת המוצא. בכך גילינו מעגל בתמורה, והוא:
\(\displaystyle \begin{pmatrix} 1 & 3 \\ 3 & 1 \end{pmatrix} \)
כמו כן, \({2}\) עובר ל- \({4}\), \({4}\) עובר ל- \({6}\), \({6}\) עובר ל- \({2}\), ובכך גילינו מעגל נוסף בתמורה והוא:
\(\displaystyle \begin{pmatrix} 2 & 4 & 6 \\ 4 & 6 & 2 \end{pmatrix} \)
נותר האיבר \({5}\), אשר עובר לעצמו, וזהו מעגל באורך אחד:
\(\displaystyle \begin{pmatrix} 5 \\ 5 \end{pmatrix} \)
התהליך שתיארנו כאן הוא הפירוק של תמורה למעגלים, שנותן את ההצגה
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 1 & 6 & 5 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 3\\ 3 & 1 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 \\ 4 & 6 & 2 \end{pmatrix} \begin{pmatrix} 5\\ 5 \end{pmatrix} \)
זוהי עובדה בסיסית, שקל להשתכנע בנכונותה, שכל תמורה ניתנת לפירוק למעגלים.
3.3 תיאור גרפי של פונקציות ותמורות
נתבונן כעת בפונקציות כלליות (לאו דווקא חד-חד-ערכיות) מהקבוצה \({\{1,2,\ldots,n\}}\) לעצמה. גם פונקציה כזו ניתן להציג בכתיב של שתי שורות, עם אותה מוסכמת כתיבה. למשל:
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 2 & 4 & 6 \end{pmatrix} \)
נוכל לתאר פונקציה ע”י גרף מכוון שבו כל איבר שולח חץ אל תמונתו תחת הפונקציה. הגרף המתאים לדוגמה הנ”ל מופיע באיור 2.
איור 2
נשים לב, שלפי הגדרת מושג הפונקציה, בתיאור הגרפי יוצא מכל קודקוד חץ אחד ויחיד. אם נצא מקודקוד כלשהו ונלך בעקבות החיצים היוצאים, נהיה חייבים במוקדם או במאוחר לבקר שוב בקודקוד שכבר היינו בו. מכאן ברור שהגרף של פונקציה חייב להכיל לפחות מעגל אחד (לצורך העניין, גם חץ מקודקוד לעצמו \({-}\) לולאה \({-}\) נחשב מעגל). באיור 2, הקודקודים \({1}\) ו- \({2}\) יוצרים מעגל אחד, והקודקוד \({6}\) מעגל נוסף. ייתכן שכל קודקוד נמצא במעגל כלשהו: זהו בדיוק המקרה שבו הפונקציה היא חד-חד-ערכית, כלומר תמורה. במקרה זה מקבלים בצורה גרפית את הפירוק למעגלים של תמורה אשר הוסבר לעיל. אם יש קודקודים שאינם באף מעגל, אז כל קודקוד כזה שולח חץ לקודקוד הנמצא במעגל, או לקודקוד השולח חץ לקודקוד הנמצא במעגל, וכו’ (ראו למשל באיור 2).
4. הוכחת ז’ויאל לנוסחת קיילי
כעת אנו מוכנים להוכיח את נוסחת קיילי באמצעות הרעיון המחוכם של ז’ויאל.
משפט. המספר \({a_n}\) של עצים מתויגים על \({n}\) קודקודים נתון ע”י \({a_n = n^{n-2}}\).
הוכחה. תחילה נשים לב שהנוסחה הנתונה שקולה ל- \({n^2a_n = n^n}\). הסתכלות זו מועילה, כי \({n^n}\) סופר משהו מוכר: זה מספר הפונקציות מ- \({\{1,2,\ldots,n\}}\) ל- \({\{1,2,\ldots,n\}}\). ומה סופר אגף שמאל? המספר \({a_n}\) סופר כמובן את העצים המתויגים על \({n}\) קודקודים. נניח שאנו בוחרים שניים מבין הקודקודים של עץ מתויג (אשר יכולים גם להיות אותו קודקוד), וקוראים להם בהתאמה שורש \({A}\) ושורש \({B}\) של העץ. אפשר לבצע את הבחירות של \({A}\) ו- \({B}\) ב- \({n^2}\) אופנים. לכן \({n^2a_n}\) הוא מספר העצים המתויגים על \({n}\) קודקודים עם ציון של שני שורשים \({A}\) ו- \({B}\).
לפיכך, אם נבנה התאמה חד-חד-ערכית ועל בין אוסף הפונקציות מהקבוצה \({\{1,2,\ldots,n\}}\) לעצמה, לבין אוסף העצים המתויגים על \({\{1,2,\ldots,n\}}\) עם ציון של שני שורשים, ינבע כי \({n^2a_n = n^n}\) ובכך תוכח נוסחת קיילי. כלומר, עלינו להראות איך מתאימים לכל פונקציה עץ מתויג עם שני שורשים; ובהינתן עץ מתויג עם שני שורשים איך משחזרים באופן יחיד את הפונקציה ממנה הוא בא.
נתחיל עם פונקציה מהקבוצה \({\{1,2,\ldots,n\}}\) לעצמה, ונדגים את בניית העץ המתויג עם שני שורשים המתאים לה עבור הפונקציה מאיור 2. ראשית, מתוך ההצגה של הפונקציה בכתיב של שתי שורות
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 2 & 4 & 6 \end{pmatrix} \)
נשאיר רק את החלקים המעגליים, מבלי לשנות את סדר הופעתם, כלומר
\(\displaystyle \begin{pmatrix} 1 & 2 & 6 \\ 2 & 1 & 6 \end{pmatrix} \)
זוהי כמובן תמורה של תת-קבוצה של \({\{1,2,\ldots,n\}}\), שנקרא לה החלק התמורתי בפונקציה. נתבונן בשורה התחתונה שקיבלנו, ונקבע את הקודקוד השמאלי ביותר להיות \({A}\) ואת הימני ביותר להיות \({B}\) (בדוגמה \({A=2, B=6}\)). כעת נבנה עץ מתויג עם שני שורשים \({A}\) ו- \({B}\) כדלקמן. תחילה, נצייר מסילה שלאורכה מופיעים הקודקודים בתמורה לפי סדר הופעתם בשורה התחתונה (בדוגמה \({2-1-6}\)). קצות המסילה הם \({A}\) ו- \({B}\) בהתאמה. כעת, נחבר את יתר הקודקודים למסילה בהתאם לחיצים היוצאים מהם בגרף של הפונקציה. התוצאה היא עץ מתויג על \({\{1,2,\ldots,n\}}\) עם שני שורשים \({A}\) ו- \({B}\), והיא מוצגת עבור הדוגמה שלנו באיור 3.
איור 3
ועכשיו, לכיוון ההפוך. נתון לנו עץ מתויג על \({\{1,2,\ldots,n\}}\) עם שני שורשים \({A}\) ו- \({B}\). בעץ יש מסילה יחידה מ- \({A}\) ל- \({B}\), וממנה נשחזר את השורה התחתונה של החלק התמורתי בפונקציה. (אם \({A=B}\), המסילה מורכבת מקודקוד בודד, והחלק התמורתי בפונקציה מורכב מלולאה אחת). ע”י כתיבת אותם קודקודים בשורה העליונה בסדר מספרי עולה, נשחזר את החלק התמורתי בפונקציה. למשל, מהעץ עם שני שורשים באיור 3 נקבל
\(\displaystyle \begin{pmatrix} 1 & 2 & 6 \\ 2 & 1 & 6 \end{pmatrix} \)
כעת, לא נותר אלא להוסיף בשורה העליונה את יתר הקודקודים תוך שמירה על סדר מספרי עולה, ולכתוב מתחת לכל קודקוד כזה את מספרו של הקודקוד הראשון בדרך ממנו אל המסילה \({A-B}\) בעץ. בדוגמה נקבל
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 2 & 4 & 6 \end{pmatrix} \)
שהיא הפונקציה ממנה יצאנו. תהליך השחזור ניתן לביצוע באופן יחיד על כל עץ עם שני שורשים, ובכך עמדנו במשימת ההוכחה. הקוראים מוזמנים לבדוק את הבנת תהליכי הבנייה והשחזור בדוגמאות נוספות, למשל הפונקציה הבאה והעץ עם שני שורשים המתאים לה באיור~4:
\(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 3 & 1 & 3 & 2 & 3 & 1 & 5 & 5 \end{pmatrix} \)
איור 4
\(^1\) אותה בעיה לעצים לא מתויגים היא בלתי פתורה, למרות שהמספרים \({u_n}\) קטנים בהרבה מ- \({a_n}\).
כתיבת תגובה