הפונקציה !n

לכל n טבעי , הביטוי ! n ( קרי : n עצרת ) מציין את המכפלה של סדרת המספרים הטבעיים היורדת מ- n עד 1 n ! = ( 1-nn () -n 2 )    321 למשל : 1 ! = 1 2 ! = 2  1 3 ! = 3  2  1  10 ! = 10  9  8  3  2  1 מסיבות שתתבהרנה בהמשך , מקובל להרחיב את הגדרת ! n גם ל- , n = 0 כך : 0 ! = 1 פונקצית העצרת היא הפונקציה f ( n ) = n ! , f : N - N לכל , n < 1 , n מתקיים : !( n ! = n  -n () -n 2 ) 2  1  = ( 1-nn כלומר פונקצית העצרת מקיימת : ( f ( n ) = n  f ( 1-n הנוסחה האחרונה , המאפשרת לחשב את ( f ( n מתוך ( , f ( n 1- מכונה נוסחת נסיגה . נוסחת הנסיגה , בצירוף הדרישה , f ( 0 ) = 1 קובעות את הערך ( f ( n של פונקצית העצרת , לכל מספר n בתחומה . נחשב לדוגמה את ( . f ( 5  f ( 5 ) = 5  f ( 4 ) = 5  4  f ( 3 ) = 5  4  3  f ( 2 ) = 5   43  2  f ( 1 ) ( = 5  4  3   21  f ( 0 לאור הדרישה f ( 0 ) = 1 אנו מקבלים : ! f ( 5 ) = 5  4  3   21 = 5 אם-כן , את פונקצית העצרת אפשר להגדיר כך : הגדרה 4 . 1 פונקצית העצרת – הגדרה באמצעות נוסחת נסיגה פונקצית העצרת היא הפונקציה f : N - N העו...  To the book