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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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