MHB How can I find |A|,having found |UA_{i}^{c}| ?

[evinda]

Hello! :)
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|$ ?

 

[Evgeny.Makarov]

Obviously, $|A|=|S_n|-|A^c|$.

 

[evinda]

Obviously, $|A|=|S_n|-|A^c|$.

So,is it $n!-n!(1-\frac{1}{e})-n!R(n) =n!(\frac{1}{e}-R(n)$ ?

 

[Evgeny.Makarov]

So,is it $n!-n!(1-\frac{1}{e})-n!R(n) =n!(\frac{1}{e}-R(n))$ ?

Yes. Also, $1/e$ that occurs in $R(n)$ can be eliminated to get
\[
|A|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
\]
By the way, such permulations are called derangements.

 

[evinda]

Yes. Also, $1/e$ that occurs in $R(n)$ can be eliminated to get
\[
|A|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
\]
By the way, such permulations are called derangements.

I understand :) Thank you very much!