Suppose that there are n persons numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that first person takes the hat i. There are n − 1 ways for the first person to choose the number i. Now there are 2 options:

1. Person i takes the hat of 1. Now the problem reduces to n − 2 persons and n − 2 hats.
2. Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons n − 1 hats (each of the remainingn − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats).

From this, the following relation is derived:

!0=1

!1=0

!2= (n-1) (!(n-1)+!(n-2))=1 (!1+!0) = 1 (0+1) = 1 * 1 = 2

!3= (n-1) (!(n-1)+!(n-2))=2 (!2+!1) = 2 (2+0) = 2 * 2 = 4

Pregenearate 2 to 12 derangement value and factorial of 2 to 12

input n

print !n/n!