נוסחת קיילי

פרופ’ דניאל קלייטמן, Daniel J. Kleitman), MIT), ארה”ב
הרצאה שניתנה במועדון המתמטי בטכניון בשנות ה-90 של המאה הקודמת

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

מסלול בגרף מהקודקוד \({x}\) לקודקוד \({y}\) הוא רשימה של צלעות כך ש:

הצלע הראשונה מכילה את \({x}\) והצלע האחרונה מכילה את \({y}\);
לכל צלע ברשימה יש קודקוד משותף עם הצלע העוקבת לה, וקודקוד אחר משותף עם הצלע הקודמת לה.

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

\({n=6}\)

kl-cy1_1

גרף

kl-cy1_2

עץ

kl-cy1_3

מעגל

במאה התשע-עשרה, קיילי \(Cayley\) שאל וענה על השאלה הבאה: כמה עצים שונים יש עם קבוצה נתונה של \({n}\) קודקודים? מאז הופיעו הוכחות רבות של התוצאה שלו. אנו מציגים כאן הוכחה שהיא אולי חדשה.

נראה קודם אם נוכל לנחש את התשובה: כדי לעשות כך נבדוק את המקרים הקטנים: למרבה המזל, עבור ערכים קטנים של \({n}\) יש רק מעט צורות שיכולות להיות לעץ, ואפשר לספור כמה עצים יש מכל צורה ללא קושי רב. זה נעשה בציור הבא.

בדרך כלל אפשר לשים את קודקודי צורה על קבוצת \({n}\) הקודקודים הנתונים (“לקרוא לקודקודי הצורה בשמות”) ב \({n!}\) אופנים שונים. אבל, אם לצורה יש סימטריה, אזי אותו עץ יתקבל מ”קריאה כלשהי בשמות” ומתמונתה ע”י פעולת סימטריה. כדי למצוא את מספר העצים השונים מכל צורה יש לחלק את \({n!}\) במספר פעולות הסימטריה שיש לצורה (במלים אחרות, בסדר חבורת הסימטריה שלה).

kl-cy2

מס’ העצים \({n}\)
\({1}\) \({n=2}\)
\({3}\) \({n=3}\)
\({16}\) \({n=4}\)
\({125}\) \({n=5}\)

מוצאים, עבור מספר העצים \({c(n)}\) על \({n}\) קודקודים: \({c(3)=3^1}\), \({c(4)=4^2}\), \({c(5)=5^3}\), וזה מביא להשערה שהתשובה היא \({c(n)=n^{n-2}}\). זה פועל אפילו עבור \({n=2}\): \({c(2)=1=2^0}\).

נבדוק את \({n=6}\), בציור מתוארות הצורות האפשריות:

kl-cy3הצורות עבור \({n=6}\)

\({360\cdot3+90+120+6=1296=6\cdot6\cdot6\cdot6}\)

אם אתם כמוני (וכמו קיילי) , אתם בוודאי כבר משוכנעים שהתשובה הכללית היא \({n^{n-2}}\).

זה מה שנוכיח. כדי לעשות זאת, נשאל קודם: מה אנו יודעים שהמספר הזה, \({n^{n-2}}\) מונה?

אם נבדוק שוב מקרים קטנים, נראה ש \({3=(1+1+1)}\), \({4^2=(1+1+1+1)\cdot(1+1+1+1)}\), ובאופן כללי \({n^{n-2}}\) הוא מכפלה של \({n-2}\) גורמים זהים שכל אחד מהם הוא סכום \({n}\) \({1}\) -ים.

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

לכן \({n^{n-2}}\) מונה את מספר הדרכים השונות לבחור אפשרות אחת מבין \({n}\) אפשרויות, \({n-2}\) פעמים נבדלות.

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

זו תהיה דרך המחשבה של הוכחתנו:

  • \({n^{n-2}}\) יכול להיכתב כמכפלה של סכומי \({1}\) -ים בסוגריים.
  • כל איבר שמתקבל אחרי פתיחת הסוגריים ניתן לתיאור ע”י “פונקציה”.
  • כל פונקציה כזו קובעת גרף מכוון.
  • כל גרף מכוון כזה מתאים לעץ מסוים וכל העצים מתקבלים באופן כזה.
  • לכן \({n^{n-2}}\) הוא מספר העצים.

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

הנה דוגמה עם \({n=5}\).

\(\displaystyle 5^3=(1+1+1+\underline{ 1}+1) (1+1+\underline{ 1}+1+1) (1+\underline{ 1}+1+1+1)\)

את האיברים המודגשים בקו מתחת אפשר לתאר ע”י ה”פונקציה” או ההתאמה \({f(3)=2}\) ,\({f(2)=3}\) ,\({f(1)=4}\). וכל איבר בפיתוח המכפלה מתואר ע”י פונקציה אחרת.

אפשר לבנות גרף מכוון שמתאים לפונקציה כזו ע”י כך שמפרשים את העובדה \({f(1)=4}\), למשל, בתור קיום צלע מכוונת מ \({1}\) ל \({4}\).

זהו, איפוא, הגרף המכוון שמתאים לפונקציה שבאה מהאיבר לעיל: kl-cy4

\({f(1)=4, f(2)=3, f(3)=2}\)

הגרפים שאנו מקבלים בצורה כזאת אינם עצים. למשל, אלה גרפים מכוונים בעוד שעצים אינם מכוונים. את זה קל לתקן: אפשר לכוון את הצלעות בכל עץ כך שיתכוונו אל הקודקוד \({n}\). אז כל עץ נהפך לגרף מכוון; אבל זה עדיין לא נראה כמו הגרפים שלנו.

kl-cy5_1

עץ

kl-cy5_2

עץ עם צלעות מכוונות לכיוון \({n}\), \({n=7}\)

כאשר מתייחסים לעצים באופן כזה, הם נבדלים מהגרפים שלנו בשלושה אופנים: בכל אחד מהם יש צלע שיוצאת מ \({n-1}\), בעוד שבגרפים שלנו איןאין בהם מעגלים, בעוד שבגרפים שלנו יכולים להיות;. בנוסף לכך, בכל עץ, המכוון באופן זה, יש צלע מכוונת ל \({n}\)בגרפים שלנו לא חייבת להיות צלע כזו.

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

איך? נסדר את המעגלים לפי הקודקוד הגדול ביותר בהם (כלומר הקודקוד שהאינדקס המספרי שלו: \({1,2,\ldots,n}\) הוא הגדול ביותר) , הגדול ביותר תחילה; ניתן למסלול שלנו להתחיל ב \({n-1}\) ולהיכנס לכל מעגל מייד אחרי הקודקוד הגדול ביותר במעגל, ולצאת אל המעגל הבא (או, אם אין יותר, אל \({n}\)) בקודקוד הגדול ביותר (ובכך תישמט הצלע מהקודקוד הגדול ביותר אל העוקב לו במעגל) . כעת אנו עוברים למעגל בעל הקודקוד השני בגודלו וחוזרים על הבניה, עד שאין יותר מעגלים.

הנה דוגמה כיצד זה נעשה: 

\({f(1)=4,\,f(2)=3,\,f(3)=2}\)

\({n-1=4}\)

kl-cy6

כדי להפוך לעץ:
הוסף צלע מ \({n-1}\) לקודקוד שאחרי הגדול ביותר במעגל: \({\{4,2\}}\)
הוסף צלע מהגדול ביותר במעגל אל המעגל הבא או אל \({n}\): \({\{3,5\}}\)
השמט את הצלע במעגל היוצאת מהקודקוד הגדול ביותר: \({\{3,2\}}\)

כדי להפוך (לבטל) את הבניה – כדי לקבל את \({G}\) מהעץ המתאים \({T}\), מצא את המסלול מ \({n-1}\) ל \({n}\) ב \({T}\); הקודקוד הגדול ביותר במסלול זה מסמן את קצה המעגל הראשון ב \({G}\). בנה מחדש מעגל זה, השמט את הצלע שיוצאת מ \({n-1}\), ועבור למעגל הבא; בנה אותו מחדש באופן דומה, והמשך עד שיצרת את \({G}\).

kl-cy7

\({G\setminus T}\) מורכב מצלע מכל מעגל – זו שיוצאת מהקודקוד הגדול ביותר במעגל.
\({T\setminus G}\) מורכב מצלע מ \({n-1}\) למעגל הראשון, צלעות מהקודקוד הגדול ביותר בכל מעגל אל העוקב לגדול ביותר במעגל הבא, ולבסוף צלע אל \({n}\). הוכחנו את נוסחת קיילי. אם אתם רוצים לשכנע את עצמכם ששיקולים אלה פועלים, נסו לצייר כמה עצים ולהפוך אותם לגרפים, לפונקציות ולאיברים בפיתוח של \({n^{n-2}}\) וללכת גם בדרך ההפוכה. התהליך של המרת מעגלים במסלול כמו שאנו עושים זאת כאן מזכיר לי עשיית מחרוזת עם חרוזים מסודרים לפי הגודל.

הערה נוספת: הפונקציה \({(x_1+x_2+\cdots+x_n)^{n-2}}\), כאשר מפתחים אותה לפי חוק הפילוג (החוק הדיסטריבוטיבי) , מורכבת מ \({n^{n-2}}\) איברים, אחד עבור כל גרף \({G}\), ולכן אחד עבור כל עץ, בדיוק כמו לעיל, פרט לכך שהאיברים אינם כולם \({1}\). באיבר שנתרם ע”י עץ מסויים יש חזקה \({{x_j}^k}\) אם \({j}\) נלקח \({k}\) פעמים בבניית האיבר המתאים מחוק הפילוג; זה אומר שהערכיות הנכנסת של הקודקוד \({j}\) ב \({G}\) היא \({k}\).

כל ערכיות ב \({T}\) היא בדיוק ב \({1}\) יותר מהערכיות הנכנסת של אותו קודקוד ב \({G}\)לכן הפונקציה לעיל היא הסכום על העצים של המכפלה עבור אינדקסים \({j}\) בין \({1}\) ו \({n}\) של \({x_j}\) מועלה לחזקה שהיא ערכיות הקודקוד \({j}\) ב \({T}\) פחות \({1}\). בסימון מתמטי זה נכתב כך: 

\(\displaystyle \prod_{j=1}^n \left((x_j)^{d_j(T)-1}\right)\)

הטענה האומרת ששתי ישויות אלה הן שוות היא הצורה החזקה המקובלת של נוסחת קיילי.

יש תריסרי הוכחות שונות לנוסחת קיילי, אבל כולן נראות קצת קשות יותר מזו שהבאנו. ההוכחה הקרובה לה ביותר ברוחה היא של \(Chen\).

2 תגובות על נוסחת קיילי

  • מאת ב‏:

    ממש מוזר. חשבתי על הנוסחה הזאת מיד לאחר שהתעוררתי (שזה היה לפני כ-10 דקות), אחרי שלא חשבתי עליה זמן רב ביותר.
    והנה אח”כ החלטתי להיכנס לגליון החדש של נטגר, ובדיוק מופיעה כתבה על הנוסחה.
    (כן כן, אני מאשים אתכם בטלפתיה מעל פרוטוקול TCP/IP.)

  • מאת יוסי כהן‏:

    :)