Welcome to our community

Be a part of something great, join today!

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
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
Jan 30, 2012
2,502
Obviously, $|A|=|S_n|-|A^c|$.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
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
Apr 13, 2013
3,723