מספר סטירלינג

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

ישנן שתי משפחות של מספרי סטירלינג:

• מספרי סטירלינג מהסוג הראשון הם המספרים $S_{1}(n,k)$ המתקבלים מן הזהות $(x)_{n}=\sum _{k\,=\,0}^{n}S_{1}(n,k)x^{k}=x(x-1)(x-2)\cdots (x-n+1)$.
• מספרי סטירלינג מהסוג השני הם המספרים $S_{2}(n,k)$ המתקבלים מן הזהות $x^{n}=\sum _{k\,=\,0}^{n}S_{2}(n,k)(x)_{k}$.

בניגוד לקודמיהם, אלה ניתנים לחישוב באמצעות הסכום

$S_{2}(n,k)={\frac {1}{k!}}\sum _{i\,=\,0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}=\sum _{i\,=\,0}^{k}{\frac {(-1)^{k-i}}{i!(k-i)!}}i^{n}$

מהשוואת המונום העליון נובע כי $S_{1}(n,n)=S_{2}(n,n)=1$.

למספרים אלה יש משמעות קומבינטורית.
$(-1)^{n-k}S_{1}(n,k)$ הוא מספר התמורות על $n$ איברים שיש להן $k$ מחזורים. למשל, $S_{1}(4,2)=11$ כי יש 8 תמורות שמבנה המחזורים שלהן הוא 3+1, ועוד 3 שהמבנה שלהן הוא 2+2.
$S_{2}(n,k)$ הוא מספר הדרכים לפרק קבוצה בת $n$ עצמים ל-$k$ תת-קבוצות לא-ריקות. למשל, $S_{2}(4,2)=7$ משום שיש שבע דרכים לפרק קבוצה בת 4 איברים לשני חלקים: ארבע שבהן יש בקבוצה אחת איבר יחיד ובשנייה שלושה, ועוד שלוש שבהן יש בכל חלק שני איברים. מספרי סטירלינג מהסוג השני מקיימים את נוסחת הרקורסיה $S_{2}(n,k)=S_{2}(n-1,k-1)+kS_{2}(n-1,k)$.

סדרת המונומים $1,x,x^{2},\ldots$ מהווה בסיס סטנדרטי לחוג הפולינומים במשתנה אחד. גם הסדרה $(x)_{0}=1,(x)_{1},(x)_{2},\ldots$ מהווים בסיס למרחב הזה, והמטריצות $(S_{1}),(S_{2})$ הן מטריצות מעבר מהבסיס הראשון לשני ובחזרה, בהתאמה. לכן הן הפוכות זו לזו: $(S_{1})(S_{2})=(S_{2})(S_{1})=1$, ומכאן הזהויות

$\sum _{k\,=\,j}^{n}S_{1}(n,k)S_{2}(k,j)=\sum _{k\,=\,j}^{n}S_{2}(n,k)S_{1}(k,j)=\delta _{jn}$

לכל $j\leq n$.

לקריאה נוספת

• Ronald Graham, Donald Knuth, Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994, pp. 257-267