הגדרה: הפרות סדר של המספרים 1,2,\ldots n זה סידור שלהם במקומות 1,2,\ldots n כך שלכל i, מספר i אינו מופיע במקום i. מספרן יסומן ע"י D_{n}.
הוכח כי מספר הפרות הסדר מקיים את נוסחת הנסיגה הבאה:
D_{n}=(n-1)\cdot(D_{n-1}+D_{n-2})
מה תנאי ההתחלה?
נסמן ב-m את הערך הנמצא במקום הראשון בהפרות הסדר. m יכול להיות כל ערך, מלבד 1, שכן מדובר בהפרות סדר (סה"כ n-1 אפשרויות). נפריד למיקרים:
- המספר m נמצא במקום הראשון בהפרות סדר ו-1 במקום ה-m. במקרה זה עלינו לסדר את שאר n-2 המספרים ב-(n-2) מקומות ולכן D_{n-2}.
- המספר m נמצא במקום הראשון בהפרות סדר ו-1 לא נמצא במקום ה-m. במקרה זה, עלינו לסדר את n-1 מספרים ב-(n-1) מקומות ולכן D_{n-1}.
מאחר ומדובר במיקרים זרים, נוכל להסיק ע"פ עקרון החיבור, כי מספר הפרות הסדר בהן m נמצא במקום הראשון הינו:
D_{n-1}+D_{n-2}
נבחר את m ב-(n-1) אפשרויות (ללא 1 שכן הוא לא יכול להיות במקום הראשון). לכן סה"כ נקבל:
D_{n}=(n-1)\cdot(D_{n-1}+D_{n-2})
עם תנאי ההתחלה הבאים:
- מתקיים D_{1}=0 - שכן 1 אינו יכול להיות במקום ה-1.
- מתקיים D_{0}=1 - שכן הווקטור הריק הוא הפרת סדר.