מזרקה (קומבינטוריקה)

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

• בשורה התחתונה כל העיגולים נוגעים אחד בשני
• כל עיגול אחר נוגע בדיוק בשני עיגולים בשורה מתחתיו

העניין העיקרי במזרקות הוא מספר המזרקות שאפשר ליצור מ-n עיגולים. המספרים המתקבלים הם:

...1,1,2,3,5,9,15,26,45,78,135,234,406,704,1222,2120,3679,6385,11081 (סדרה A005169 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים)

הגדרות שקולות

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

נוסחת נסיגה

נשתמש בהגדרה השקולה. נסמן ב-(P(n,k את מספר הסדרות שסכומן n, המספר הראשון שלהן הוא k, וכל איבר הוא לכל היותר אחד יותר מקודמו. אז נקבל את יחס הנסיגה הבא:

$P(n,k)={\begin{cases}0&k>n\\1&k=n\\\sum _{i=1}^{k+1}P(n-i,i)&n>k\end{cases}}$

ומספר המזרקות מגודל n הוא (P(n,1.

פונקציה יוצרת

הפונקציה היוצרת של הסדרה היא: ${\begin{aligned}f(n)&=&{\dfrac {1}{1-{\dfrac {x}{1-{\dfrac {x^{2}}{1-{\dfrac {x^{3}}{\cdots }}}}}}}}\,\end{aligned}}$

יתרה, מכך, אם נסמן ב-(f(n,k את מספר המזרקות שיש להן k עיגולים בבסיסן, הפונקציה היוצרת היא: ${\begin{aligned}f(n,k)={\dfrac {1}{1-{\dfrac {xy}{1-{\dfrac {x^{2}y}{1-{\dfrac {x^{3}y}{\cdots }}}}}}}}\end{aligned}}$

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

• Odlyzko, A. M. and Wilf, H. S, The editor’s corner: n coins in a fountain, Amer. Math. Monthly 95 840–843