עצרת (מתמטיקה)

בעברית, עצרת (באנגלית: Factorial) היא המכפלה של כל המספרים הטבעיים מ‑1 ועד n. למשל, 4 עצרת שווה ל‑1 כפול 2 כפול 3 כפול 4, כלומר 24. הסימון המקובל הוא סימן קריאה אחרי המספר: n!. הסימון הוצע על ידי כריסטיאן קראמפ במאה ה‑19.

העצרת מוגדרת רקורסיבית (קרי בהסתמכות על ערכים קודמים): n! = (n‑1)! כפול n, עם התנאי ההתחלתי 0! = 1. הסבר פשוט לכך הוא שיש דרך אחת לסדר אפס איברים, הדרך הריקה. גם מוסכמה מתמטית קובעת שמכפלה ריקה שווה ל‑1.

לקירוב של n! עבור n גדול משתמשים בהמרת הלוג של המכפלה לסכום ולאינטגרל. הערכה מדויקת יותר מובילה לנוסחת סטרלינג, שמקשרת בין n! לבין הביטוי (n/e)^n והמקדם sqrt(2πn). נוסחת סטרלינג נותנת קירוב טוב לערכי עצרת גדולים.

העצרת גדלה מאוד מהר, הרבה יותר מפי פונקציות פולינומיות וממספרים בהצמדה חזקות. המשמעות היא שעבור n גדולים מאוד, n! עולה יותר מהר אפילו מהצמדה a^n לכל קבוע a.

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

עצרת מופיעה גם בפיתוחים טוריים. למשל, הסכום של 1/n! מייצג את המספר e. כמו כן הפיתוח של e^x משתמש ב‑n! במחלקות החזקות x^n/n!.

פונקציית גמא (Gamma) היא הרחבה של העצרת למספרים שאינם שלמים. היא מקיימת Γ(n+1)=n! עבור n טבעי, ולכן משמשת להכללות אנליטיות של העצרת.

עצרת כפולה (Double factorial) היא גרסה שבה מכפילים רק מספרים בעלי אותה זוגיות, למשל n!! = n·(n‑2)·(n‑4)·… עד לסוף. זו פונקציה דומה אך שונה מהעצרת הרגילה.

רוב שפות התכנות אין להן פונקציית עצרת מובנית, אך קל לכתוב אחת בלולאה או רקורסיה. בכלי חישוב קיימת פונקציה מוכנה; באקסל היא נקראת FACT. גודל התוצאה גדל מהר, ולכן חישוב מדויק של n! מוגבל על ידי ארכיטקטורת המחשב: במילה של 32 סיביות ניתן לייצג עד 12!, וב‑64 סיביות עד 21!. באקסל ניתן לחשב עד 170!, ובמחשבון Windows10 (64 סיביות) מצויין גבול גדול יותר (כ־3248!, סדר גודל של 10^9997).

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

עצרת היא מכפלה של כל המספרים מ‑1 עד מספר נתון. כלומר לוקחים 1 וכופלים ב‑2, ב‑3 וכדומה עד שמגיעים ל‑n. דוגמה: 4 עצרת שווה ל‑1 כפול 2 כפול 3 כפול 4, וזה 24.

למה 0! שווה 1? כי יש דרך אחת לסדר אפס פריטים. זו הדרך הריקה.

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

העצרת גדלה מאוד מהר. גדלה מהר יותר מכל פולינום או רוב החזקות.

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

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

פונקציית גמא (פונקציה שמרחיבה את העצרת) מאפשרת להשתמש ברעיון גם למספרים שאינם שלמים.

עצרת כפולה מכפילה רק כל שני מספרים (כל פעם מקפיצה ב‑2). זו וריאציה של העצרת.

מחשבונים ותוכנות יודעים לחשב עצרת, אבל יש להם גבול. במחשבים רגילים אפשר לבטא עד 12! או 21! בלי בעיה. בתוכנות כמו אקסל אפשר לחשב עד 170!.

עצרת משמשת כדי לספור סידורים ולפתור בעיות ארגון וסידור בחשבון.