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

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

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

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

סדרת המונומים $\ 1,x,x^{2},x^{3},\dots$ מהווה בסיס סטנדרטי לחוג הפולינומים במשתנה אחד. גם הסדרה $\ (x)_{0}=1,(x)_{1},(x)_{2},(x)_{3},\dots$ מהווים בסיס למרחב הזה, והמטריצות (s) ו-(S) הן מטריצות מעבר מהבסיס הראשון לשני ובחזרה, בהתאמה. לכן הן הפוכות זו לזו: $\ (S)(s)=1$, ומכאן הזהויות $\sum _{k=j}^{n}s(n,k)S(k,j)=\delta _{jn}$ ו- $\sum _{k=j}^{n}S(n,k)s(k,j)=\delta _{jn}$ לכל $j\leq n$.