1
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.