# In how many ways can students sit

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}

• – Barry Cipra Jun 16 '16 at 13:34

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!}. }$

• Sorry, I was just going to complete my answer. – Tiziano Nicolardi Jun 16 '16 at 17:26