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

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

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

מספרי סטירלינג מהסוג הראשון הם המספרים $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$ , ומכאן הזהויות