הצגת המקור של הדף "מזרקה (קומבינטוריקה)"

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

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

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

<math>P(n,k) =
\begin{cases}

0 & k>n \\
1 & k=n \\
\sum_{i=1}^{k+1}P(n-i,i) & n>k
\end{cases}</math>

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

==פונקציה יוצרת==
ה[[פונקציה יוצרת|פונקציה היוצרת]] של הסדרה היא:
<math>
\begin{align}
f(n)& = & \dfrac{1}{1-\dfrac{x}{1-\dfrac{x^2}{1-\dfrac{x^3}{\cdots}}}} \,
\end{align}
</math>

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

==קישורים חיצוניים==
* [[אנדרו אודליז'קו|Odlyzko, A. M]]. and Wilf, H. S, [https://www.math.upenn.edu/~wilf/website/Coins%20in%20a%20fountain.pdf The editor’s corner: n coins in a fountain], Amer. Math. Monthly 95 840–843
[[קטגוריה:סדרות של שלמים]]