עצרת

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
n  !n
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
25 ~1025
50 ~1064
100 ~10158
1000 ~102567
10000 ~1035659
100000 ~10456573
1000000 ~105565709
10000000 ~1065657059
10100 ~1010102

במתמטיקה, עֲצֶרֶת היא מכפלת כל המספרים הטבעיים מ-1 ועד למספר נתון.

למשל, "4 עצרת" היא המכפלה \ 1\times 2 \times 3 \times 4 = 24.

בעקבות הצעתו של המתמטיקאי כריסטיאן קראמפ משנת 1808, מקובל לסמן את העצרת בסימן "!", כלומר, \ n! = 1 \times 2 \times \cdots \times n.

העצרת היא פעולה אונארית שאותה אפשר להגדיר ברקורסיה לפי הנוסחה \ n! = (n-1)! \cdot n ותנאי ההתחלה \ 0!=1.

משמעות קומבינטורית[עריכת קוד מקור | עריכה]

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

העצרת מופיעה בספר יצירה הקדום (פרק רביעי), ובעקבותיו גם במקורות רבים אחרים במיסטיקה היהודית. תפקידה שם הוא לספור את המלים השונות שאפשר להרכיב מאותיות נתונות, תוך שימוש בכל האותיות וללא חזרה, והיא נקראת "בניה" - "שתי אבנים בונות שני בתים, שלוש אבנים בונות ששה בתים, ...". הספר מגיע עד לחישוב של 7 עצרת, ו"מכאן ואילך, צא וחשוב [וחשב], מה שאין העין יכולה לראות, ואין הפה יכולה לדבר, ואין האזן יכולה לשמוע".[1]

הערך \ 0![עריכת קוד מקור | עריכה]

יש בדיוק דרך אחת לסדר 0 איברים (היינו, לא לשבץ אף איבר באף מקום), ולכן \ 0! = 1. תוצאה זו מתאימה למוסכמה לפיה ערכה של מכפלה ריקה הוא תמיד 1, וכן להגדרת העצרת באינדוקציה (\ 1! = 1 \cdot 0!).

קירוב[עריכת קוד מקור | עריכה]

עבור \ n גדול, ניתן להשיג קירוב טוב לערך של \ n! באמצעות נוסחת סטירלינג, שקובעת כי n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n.

קצב הגידול[עריכת קוד מקור | עריכה]

ערכיה של הפונקציה נוסקים במהירות רבה ביחס לפונקציות נפוצות אחרות (דוגמת פולינומים ואף פונקציות מעריכיות). נוסחת סטרלינג מראה שעבור n גדול מספיק, מתקיים \ a^n < n! < n^n לכל a קבוע.

פונקציית גמא[עריכת קוד מקור | עריכה]

פונקציית גמא היא פונקציה מרוכבת המהווה מעין הכללה של פונקציית העצרת למספרים שאינם בהכרח שלמים. הפונקציה מוגדרת על כל המישור המרוכב למעט הנקודות \ 0,-1,-2,\cdots, לפי האינטגרל \ \Gamma (z+1) = \int_0^{\infty}{ e^{-t} t^z \ dt}. באמצעות אינטגרציה בחלקים ניתן לראות שהיא מקיימת את הזהות \ \Gamma (z+1) = z \cdot \Gamma (z). חישוב ישיר מראה ש- \ \Gamma(1) = 1, ולכן \ n! = \Gamma (n+1) לכל n טבעי.

עצרת כפולה[עריכת קוד מקור | עריכה]

עצרת כפולה (Double factorial) היא פונקציה המזכירה את העצרת אך בה מוכפלים רק ערכים בעלי אותה זוגיות. עבור n שלם ואי שלילי מוגדרת העצרת הכפולה n!! = \prod_{k=0}^m (n-2k) = n (n-2) (n-4) \cdots , כאשר m=\lceil n/2 \rceil - 1..

מימוש בתוכנה[עריכת קוד מקור | עריכה]

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

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

הגידול המהיר בערך התוצאה של פונקציית העצרת גורם לכך שבמסגרת המגבלות של החומרה והתוכנה מוגבל חישוב \ n! לערכי \ n קטנים יחסית. התוצאה הגדולה ביותר שניתן לרשום במילה של 32 סיביות היא \ 12!, ובמילה של 64 סיביות - \ 20!. באקסל ניתן לחשב עד \ 170!, שהיא העצרת הגדולה ביותר שקטנה מ-21,024 (מספר בן 1,024 סיביות). ערכי עצרת גדולים מחושבים בדרך כלל באמצעות נוסחת סטירלינג, הנותנת קירוב של התוצאה. בתורת המספרים ובקומבינטוריקה נחוץ לעתים חישוב עצרת לערכים גדולים מאוד. לשם כך נדרשת כתיבה של פונקציה מיוחדת, ונוצר צורך בבחירת אלגוריתם יעיל, כדי לקבל תוצאות תוך זמן סביר.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ספר יצירה, סעיף 40