计数与随机变量

容斥原理

利用好：

$\overline{A} \cap \overline{B}=\overline{A \cup B}$

$|A\cap B|=|A \cup B|-|A|-|B|\\ |A \cup B|=|A|+|B|-|A \cap B|$

加法原理

要求对分类的标准非常熟悉，不重不漏。

乘法原理

特殊优先。

递推计数

圆环染色

$a_n=(m-1)a_{n-2}+(m-2)a_{n-1}$

错排

$a_n=(n-1)(a_{n-1}+a_{n-2})$

$|\overline{A_1}\cap\overline{A_2}\cdots\overline{A_n}|=U-|{A_1}\cup A_2 \cup A_3 \cdots \cup A_n|$

$|A_1|=(n-1)!,|A_1\cap A_2|=(n-2)!\cdots$

分布

两点分布、超几何分布、二项分布、几何分布。

$D(X)=E(X^2)-(E(X))^2$

只有当 $X_1,X_2$ 独立时，

$D(X_1+X_2)=D(X_1)+D(X_2)$

ref:https://blog.csdn.net/The_OIer/article/details/114710931

这里 $E(AB)=E(A)E(B)$ 的条件是 $A$ 与 $B$ 独立。