מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/עצרת

לפני שנתחיל בלימודי הקומבינטוריקה נכיר ביטוי שימושי שמופיע רבות בפתרון בעיות קומבינטוריות: העצרת.

עצרת היא דרך מקוצרת לרשום מכפלה של מספרים עוקבים. היא מוגדרת רק עבור מספרים טבעיים ($1,2,3,\ldots$) ואפס.

הגדרה 1: עצרת $n!=1\cdot 2\cdot 3\cdots n$ הוא כפל המספרים מאחד ועד האיבר ה-$n$

דוגמה 1: שימוש בעצרת $1!=1$ $2!=1\cdot 2=2$ $3!=1\cdot 2\cdot 3=6$ $4!=1\cdot 2\cdot 3\cdot 4=24$

משפט 1: $n!=(n-1)!\cdot n$ לכל $n>1$ מאחר שהעצרת היא מכפלה של האיברים מהאיבר אחד ועד האיבר ה-$n$ ניתן לחשב את העצרת עד האיבר $(n-1)!$ ולהכפיל ב-$n$. $n!=\underbrace {1\cdot 2\cdot 3\cdots (n-1)} _{(n-1)!}*n$

הגדרה 2: $0!=1$ ההגדרה אינה שרירותית לחלוטין. על פי ההגדרה הבסיסית של עצרת, $0!$ הוא "מכפלה ריקה", שכן ביטוי זה מסמל את מכפלת כל המספרים הטבעיים הגדולים או שווים ל־1 וקטנים או שווים ל־0, ולא קיים אף מספר כזה. ניתן לצפות כי למכפלה ריקה יהיה ערך נייטרלי לכפל (להבדיל מכפל במספר 0) שכן אם נפרק ביטוי כלשהו לעצמו ולמכפלה ריקה, לא נרצה שערכו ישתנה. הערך הנייטרלי לכפל הוא 1.