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

אודות מחשבון זה

מספרי סטירלינג מגיעים בשתי משפחות ששתיהן מפרקות n עצמים סביב המספר השלם k, אך הן סופרות דברים שונים. מספרי סטירלינג מהסוג הראשון, s(n,k), סופרים תמורות של n איברים המתפרקות בדיוק ל-k מעגלים זרים; מספרי סטירלינג מהסוג השני, S(n,k), סופרים את הדרכים לחלק קבוצה של n איברים בדיוק ל-k תת-קבוצות לא ריקות ולא מסודרות. שתיהן מקיימות יחסי נסיגה פשוטים — S(n,k) = k·S(n−1,k) + S(n−1,k−1), למשל — וכך המחשבון בונה אותן ממקרים קטנים יותר.

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