סדרת המסעדן העצלן

סדרת המסעדן העצלן (באנגלית: Lazy caterer's sequence) או המספרים המצולעיים המרכזיים (באנגלית: Central polygonal numbers) מתארים את המספר המרבי של חתיכות של מעגל שניתן ליצור עם מספר נתון של חיתוכים ישרים. לדוגמה, שלושה חיתוכים של מעגל ייצרו שש חתיכות עם כולם נפגשים בנקודה מסוימת בתוכו, אך שבע אם לא.

פנקייק חתוך לשבע חתיכות בשלושה חיתוכים ישרים

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

זוהי בעיה הקשורה בסידור ישרים, קיימים לה מקבילים מממדים גבוהים יותר: מספרי העוגה (Cake number) עבור מרחב תלת-ממדי ובעיות סידור על-מישורים (Arrangement of hyperplanes) עבור מרחבים ממימד גבוה מ-3.

הסדרה ונוסחה

מספר החתיכות המקסימלי (p) שניתן לקבל מ-n חיתוכים ישרים היא המספר המשולשי ה-n-י ועוד אחד (OEIS A000124)

מספר החתיכות המקסימלי (p) שניתן לקבל מ-n חיתוכים ישרים (כאשר $n\geq 0$) נתון על ידי הנוסחה $p={\frac {n^{2}+n+2}{2}}$, אותה ניתן לבטא באמצעות מקדמים בינומיים בצורה $p=1+{\dbinom {n+1}{2}}={\dbinom {n}{0}}+{\dbinom {n}{1}}+{\dbinom {n}{2}}$.

סדרת המסעדן העצלן (בירוק) וסדרות סידור על-מישורים נוספות עם סימון OEIS במשולש ברנולי

האיבר ה-n-י בסדרת המסעדן העצל הוא אחד ועוד המספר המשולשי ה-n-י, ולכן העמודה השלישית במשולש ברנולי ($k=2$) מייצגת סדרה זו עבור $n\geq 2$.

בנוסף ניתן לקבל את הסדרה מסכום שלושת האיברים הראשונים בכל שורה במשולש פסקל, או האיבר הראשון בכל שורה במשולש פלויד . ההפרש בין האיבר ה-n-י בסדרה לבין האיבר שלפניו הוא n.

לפיכך, סדרה זו (סדרה A000124 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים), המתחילה ב-$n=0$, היא:

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211...

המקבילה התלת־ממדית של בעיית המסעדן העצלן היא מספרי העוגה , בה ההפרש בין האיבר ה-n-י לבין האיבר שלפניו הוא המספר ה-n בסדרת המסעדן העצלן.

הוכחה

GIF המתאר את החיתוכים העוקבים של סדרת המסעדן העצלן.

נסמן ב-$p=f(n)$ את מספר הפרוסות המרבי שנוצר מ-$n$ חיתוכים ישרים.

כדי להשיג את המספר המרבי של פרוסות, החיתוך ה-n-י צריך לחצות את כל שאר החיתוכים הקודמים בתוך המעגל מבלי לחצות שום מפגש בין שניים כאלו. לפיכך, הקו ה-n-י עצמו נחתך ב-$n-1$ מקומות, ויוצר n חתיכות נוספות. לפיכך, המספר הכולל של הפרוסות לאחר $n$ חיתוכים הוא $f(n)=n+f(n-1)$.

נוסחת נסיגה זו ניתנת לפתירה. אם נרחיב את $f(n-1)$ לפי נוסחה זו נקבל $f(n)=n+(n-1)+f(n-2)$

וברקורסיה נרחיב את הביטויים עד שהביטוי האחרון יצטמצם ל-$f(0)$, כלומר $f(n)=n+(n-1)+(n-2)+\cdots +1+f(0)$.

מכיוון ש-$f(0)=1$ (לפני כל החיתוכים קיימת פרוסה יחידה, המעגל השלם), ניתן לכתוב את המשוואה בצורה $f(n)=1+(1+2+3+\cdots +n)$, וביטוי זה ניתן לפישוט באמצעות הנוסחה לסכום סדרה חשבונית:

$f(n)=1+{\frac {n(n+1)}{2}}={\frac {n^{2}+n+2}{2}}$.

קישורים חיצוניים

• סדרה A000124 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים