הצגת המקור של הדף "מספר סטירלינג"

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

ישנן שתי משפחות של מספרי סטירלינג:
*'''מספרי סטירלינג מהסוג הראשון''' הם המספרים <math>S_1(n,k)</math> המתקבלים מן הזהות <math>(x)_n=\sum_{k\,=\,0}^nS_1(n,k)x^k=x(x-1)(x-2)\cdots(x-n+1)</math>.
*'''מספרי סטירלינג מהסוג השני''' הם המספרים <math>S_2(n,k)</math> המתקבלים מן הזהות <math>x^n=\sum_{k\,=\,0}^nS_2(n,k)(x)_k</math>.
:בניגוד לקודמיהם, אלה ניתנים לחישוב באמצעות הסכום
::<math>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</math>
מהשוואת המונום העליון נובע כי <math>S_1(n,n)=S_2(n,n)=1</math>.

למספרים אלה יש משמעות קומבינטורית.{{ש}}
<math>(-1)^{n-k}S_1(n,k)</math> הוא מספר ה[[תמורה (מתמטיקה)|תמורות]] על <math>n</math> איברים שיש להן <math>k</math> [[מחזור (תורת החבורות)|מחזורים]]. למשל, <math>S_1(4,2)=11</math> כי יש 8 תמורות שמבנה המחזורים שלהן הוא 3+1, ועוד 3 שהמבנה שלהן הוא 2+2.{{ש}}
<math>S_2(n,k)</math> הוא מספר הדרכים לפרק קבוצה בת <math>n</math> עצמים ל-<math>k</math> תת-קבוצות לא-ריקות. למשל, <math>S_2(4,2)=7</math> משום שיש שבע דרכים לפרק קבוצה בת 4 איברים לשני חלקים: ארבע שבהן יש בקבוצה אחת איבר יחיד ובשנייה שלושה, ועוד שלוש שבהן יש בכל חלק שני איברים. מספרי סטירלינג מהסוג השני מקיימים את נוסחת הרקורסיה <math>S_2(n,k)=S_2(n-1,k-1)+kS_2(n-1,k)</math>.

סדרת המונומים <math>1,x,x^2,\ldots</math> מהווה בסיס סטנדרטי לחוג הפולינומים במשתנה אחד. גם הסדרה <math>(x)_0=1,(x)_1,(x)_2,\ldots</math> מהווים בסיס למרחב הזה, והמטריצות <math>(S_1),(S_2)</math> הן [[מטריצת מעבר|מטריצות מעבר]] מהבסיס הראשון לשני ובחזרה, בהתאמה. לכן הן הפוכות זו לזו: <math>(S_1)(S_2)=(S_2)(S_1)=1</math>, ומכאן הזהויות
:<math>\sum_{k\,=\,j}^nS_1(n,k)S_2(k,j)=\sum_{k\,=\,j}^nS_2(n,k)S_1(k,j)=\delta_{jn}</math>
לכל <math>j\le n</math>.

==לקריאה נוספת==
<div class="mw-content-ltr">
* [[רונלד גראהם|Ronald Graham]], [[דונלד קנות'|Donald Knuth]], Oren Patashnik, '''Concrete Mathematics: A Foundation for Computer Science''', Addison-Wesley, 1994, pp. 257-267
</div>

[[קטגוריה:קומבינטוריקה]]