There are N students numbered from 1 to N standing in front of N chairs numbered from 1 to N. What is the number of ways the students can sit such that they don't sit on their own chairs? Student i cannot sit on chair i in none of the arrangements.
Example: when N = 4, {4,1,3,2} is not a valid arrangement as 3rd student sits on 3rd chair which is not allowed. {4,3,2,1} is allowed
Eg: when N = 2 there is only 1 possible arrangement, {2,1}
Eg: when N = 3 there are 2 arrangements, {2,3,1},{3,1,2}
It is the number of permutations without any fixed point.
$n! - |\cup^n_{i=1} A_i|$
where $A_i = \{ {f:\{1,...,n\}->\{1,...n\} \space \text {such that} \space f(i)=i\}}$
$|\cup^n_{i=1} A_i|$ can be counted via inclusion-exclusion criteria.
${|\cup^n_{i=1} A_i| = \\ + |A_1| + |A_2| + ... + |A_n|\\ - ( |A_1 \cap A_2| + |A_1 \cap A_3| + ...)\\ + ( |A_1 \cap A_2 \cap A_3| + ... )\\ ...\\ + (-1)^{n+1} |A_1 \cap ... \cap A_n| = \\ \sum ^n_{i=1} (-1)^{i+1}\binom n i (n-i)! = \\ \sum ^n_{i=1} (-1)^{i+1} {n! \over i!}. }$
Thus:
${n! - |\cup^n_{i=1} A_i| = \\ n! - \sum ^n_{i=1} (-1)^{i+1} {n! \over i!} = \\ n! ( 1 - \sum ^n_{i=1} (-1)^{i+1} {1 \over i!}) = \\ n! \sum ^n_{i=0} (-1)^{i} {1 \over i!}. }$
