Como se calcula o número de desarranjos !n de n elementos?

!n = n! \displaystyle\sum_{k=0}^n \frac{(-1)^k}{k!}

Explicação:
Essa expressão vem da inclusão-exclusão e conta as permutações sem pontos fixos, ou seja, nenhuma das n posições permanece com seu elemento original.

Exemplo:
Para n=4, calcula-se
\( !4 = 4!\left(1-1+\tfrac{1}{2}-\tfrac{1}{6}+\tfrac{1}{24}\right)\)
\( =24\left(0+\tfrac{1}{2}-\tfrac{1}{6}+\tfrac{1}{24}\right)=24\cdot\tfrac{3}{8}=9\).
Interpretando, se 4 pessoas trocam chapéus sem ninguém ficar com o próprio, existem 9 maneiras possíveis.