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

evinda

Well-known member
MHB Site Helper
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

Well-known member
MHB Math Scholar
Obviously, $|A|=|S_n|-|A^c|$.

evinda

Well-known member
MHB Site Helper
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

Well-known member
MHB Math Scholar
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

Well-known member
MHB Site Helper
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!!!