מספר סטרלינג

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

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

• מספרי סטרלינג מהסוג הראשון הם המספרים <math>S_1(n,k)</math> המתקבלים מן הזהות <math>(x)_n=\sum_{k\,=\,0}^nS_1(n,k)x^k=x(x-1)(x-2)\cdots(x-n+1)</math>.
• מספרי סטרלינג מהסוג השני הם המספרים <math>S_2(n,k)</math> המתקבלים מן הזהות <math>x^n=\sum_{k\,=\,0}^nS_2(n,k)(x)_k</math>.

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

<math>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</math>

מהשוואת המונום העליון נובע כי <math>S_1(n,n)=S_2(n,n)=1</math>.

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

סדרת המונומים <math>1,x,x^2,\ldots</math> מהווה בסיס סטנדרטי לחוג הפולינומים במשתנה אחד. גם הסדרה <math>(x)_0=1,(x)_1,(x)_2,\ldots</math> מהווים בסיס למרחב הזה, והמטריצות <math>(S_1),(S_2)</math> הן מטריצות מעבר מהבסיס הראשון לשני ובחזרה, בהתאמה. לכן הן הפוכות זו לזו: <math>(S_1)(S_2)=(S_2)(S_1)=1</math>, ומכאן הזהויות

<math>\sum_{k\,=\,j}^nS_1(n,k)S_2(k,j)=\sum_{k\,=\,j}^nS_2(n,k)S_1(k,j)=\delta_{jn}</math>

לכל <math>j\le n</math>.

לקריאה נוספת

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