משפט אוילר על חלוקת מצולעים

בקומבינטוריקה, משפט אוילר על חלוקת מצולעים (באנגלית: Euler’s Theorem of Polygon Division) עוסק במספר הטריאנגולציות של מצולע קמור, כלומר מספר החלוקות האפשרי שלו למשולשים באמצעות העברת אלכסונים שלו כך שלא יחתכו אחד את השני. אוילר מצא ביטוי מתמטי כללי הפותר את הבעיה, ולמעשה גילה את הדוגמה הראשונה לסדרת המספרים הידועה כמספרי קטלן. לבעיה ישנה מספר וריאציות, והערך הזה עוסק בווריאנט בו יש לחלק את הקודקודים של המצולע לזוגות באמצעות קווים שאינם חותכים אחד את השני. אם נסמן ב-$E_{2n}$ את מספר החלוקות של מצולע בעל 2n קודקודים, במקרה זה התוצאה של אוילר קובעת כי: $E_{2n}=C_{n}$, כאשר $C_{n}$ הוא מספר קטלן ה-nי.

תיאור הבעיה; רקע היסטורי

את הבעיה הציע המתמטיקאי לאונרד אוילר לחברו כריסטיאן גולדבך במכתב משנת 1751. את הבעיה ניתן לתאר כך: בכמה דרכים שונות ניתן לחלק מצולע קמור בעל n קודקודים לזוגות (כאשר n חייב להיות זוגי), כך שהקווים שמחברים כל זוג נקודות לא יחתכו אחד את השני. במקרה של מצולע בעל 4 קודקודים הפתרון פשוט והינו 2 חלוקות. אוילר שיער במכתבו את הביטוי הכללי לסדרת הערכים, ונתן ביטוי לפונקציה היוצרת של סדרת המספרים. אולם, אוילר התוודא לאחר קבלת הביטוי כי: "תהליך האינדוקציה שהפעיל לפתרון הבעיה היה מאוד מפרך, ושהוא אינו מטיל ספק שניתן להגיע לאותה תוצאה בקלות רבה יותר". גולדבך השיב שהפונקציה היוצרת של אוילר מקיימת את המשוואה הפונקציונלית $1+xC(x)=C(x)^{\frac {1}{2}}$. אוילר בתגובה השיב במכתב משלו, ונתן פרטים נוספים לגבי הגזירה של הפונקציה היוצרת, אך הוא עדיין לא השלים את ההוכחה. מאוחר יותר, אוילר שיתף את המתמטיקאי Johann Andreas von Segner בבעיה שהעסיקה אותו ואת גולדבך, וזה פרסם בתגובה מאמר ב-1758 עם הוכחה ליחס הנסיגה שמקיימים הערכים בסדרה. אוילר זיהה שהקשר הרקורסיבי שהוא עצמו "החמיץ" הוא בדיוק החלק החסר בהוכחה שלו, ובסיום 1758 אוילר, גולדבך ו-Segner הרכיבו הוכחה שמספר הטריאנגולציות של מצולע קמור עם n + 2 צלעות הוא: $C_{n}={\frac {1}{n+1}}{2n \choose n}$.

פתרון הבעיה

קבלת הנוסחה הרקורסיבית

מספר הטריאנגולציות של משושה קמור. הבעיה אליה מתייחס האיור מתייחסת לוריאנט של המשפט שעוסק במספר הטריאנגולציות של מצולעים קמורים, ולא במספר הזיווגים של קודקודי המצולע. במקרה זה של הבעיה מתקיים: $E_{n}=C_{n-2}$, בפרט $E_{6}=C_{4}$ ואכן למשושה באיור יש 14 טריאנגולציות.

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

$E_{2n}=E_{0}E_{2n-2}+E_{2}E_{2n-4}+...+E_{r}E_{2n-2-r}+...+E_{2n-2}E_{0}$.

בדרך זו מתקבלים בקלות 5 הערכים הלא טריוויאליים הראשונים בסדרה:

$E_{4}=2,E_{6}=5,E_{8}=14,E_{10}=42,E_{12}=132$

קבלת הביטוי הכללי

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