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

בקומבינטוריקה, מזרקה היא סידור עיגולים בשורות כך שמתקיימים התנאים הבאים:
 בשורה התחתונה כל העיגולים נוגעים אחד בשני
 כל עיגול אחר נוגע בדיוק בשני עיגולים בשורה מתחתיו
העניין העיקרי במזרקות הוא מספר המזרקות שאפשר ליצור מ-n עיגולים. המספרים המתקבלים הם:
...1,1,2,3,5,9,15,26,45,78,135,234,406,704,1222,2120,3679,6385,11081 ()

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

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

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

פונקציה יוצרת
הפונקציה היוצרת של הסדרה היא:

יתרה, מכך, אם נסמן ב-(f(n,k את מספר המזרקות שיש להן k עיגולים בבסיסן, הפונקציה היוצרת היא:

קישורים חיצוניים
 Odlyzko, A. M. and Wilf, H. S, The editor’s corner: n coins in a fountain, Amer. Math. Monthly 95 840–843
קטגוריה:סדרות של שלמים