zcmimi's blog

arrow_back错排问题共1篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

这个显然是错排问题

A_ii在位置i上的所有排列

ans=|\overline A_1\bigcap \overline A_2 \bigcap ...\bigcap \overline A_n|

=|N|

-(|A_1|+|A_2|+...+|A_n|)

+(|A_1\bigcap A_2|+...+|A_{n-1}\bigcap A_n|)

-\ ...

+ (-1)^n |A_1\bigcap A_2\bigcap ... \bigcap A_n

=n!- {n\choose 1}\cdot (n-1)! + {n\choose 2}\cdot (n-2)! - ...\ + (-1)^n {n\choose n}

=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}) = D_n

1/1
Search
search