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

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

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

• מספרי סטירלינג מהסוג הראשון הם המספרים $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}(\genfrac{}{}{0ex}{}{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)+k{S}_2(n-1,k)$.

סדרת המונומים $1,x,x^2,\dots$ מהווה בסיס סטנדרטי לחוג הפולינומים במשתנה אחד. גם הסדרה $(x{)}_0=1,(x{)}_1,(x{)}_2,\dots$ מהווים בסיס למרחב הזה, והמטריצות $(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\le n$.

לקריאה נוספת

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