- Thread starter
- #1

- Apr 13, 2013

- 3,836

I am looking at an exercise,that asks me to find $|A|$,where $A=\{\sigma \in S_{n}:\sigma(i) \neq i \forall i=1,...,n \}$

I found that $|A_{1}|=\{ \sigma \in S_{n}:\sigma(1) \neq 1 \} |=(n-1)!(n-1) $ ,from which we get that : $|A_{i}|=\{ \sigma \in S_{n}:\sigma(i) \neq i \} |=(n-1)!(n-1) $

$A=\bigcap_{i \in[n]} A_{i}$ and $A^{c}=U A_{i}^{c}$

$$|U A_{i}^{c}|=\sum_{k=1}^{n}(-1)^{k-1}\sum_{J \subseteq [n],|J|=k}|\bigcap_{i \in J} A_{i}^{c}|=n!(1-\frac{1}{e})+n!R(n) ,\text{ where } R(n)=\frac{1}{e}-\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}$$

But,how can I find $|A|$ ?