מחשבון תת-עצרת

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

התת-עצרת !n, המכונה גם מספר האי-הסדרים של n, סופרת את התמורות של n עצמים שבהן שום עצם לא מגיע למקומו המקורי. היא מוגדרת לפי !n = n! · Σ(k=0 to n) (−1)^k/k!, ומתקרבת מאוד ל-n!/e עבור n גדול — למעשה !n הוא המספר השלם הקרוב ביותר ל-n!/e. לדוגמה !4 = 9: מתוך 24 התמורות של 4 פריטים, רק 9 משאירות כל פריט לא במקומו.

ההמחשה הקלאסית היא "בעיית בדיקת הכובעים" (או "בעיית המכתבים שהועברו בטעות"): אם n אנשים מפקידים את כובעיהם והם מוחזרים באקראי, !n הוא מספר הדרכים שבהן כל אדם ואדם מקבל בחזרה כובע לא שלו. סטודנטים לקומבינטוריקה, קורסי הסתברות וחסידי חידות משתמשים בחישובי התת-עצרת לפתרון בעיות אי-סדרים, והמושג מתרחב גם לקריפטוגרפיה ותורת הקידוד בכל מקום שבו חשובות תמורות שבהן "שום דבר לא נשאר במקומו המקורי".