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

מספרי סטירלינג הם מספרים דמויי המקדמים הבינומיים, המופיעים במגוון בעיות קומבינטוריות. המספרים נקראים על-שם ג'יימס סטירלינג, שחקר אותם במאה ה-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 $.