组合分析与概率论公理
$\quad\\$
排列组合记号
$\quad\\$
排列:将$n$个不同的物体与$1$到$n$的自然数之间建立一个双射，方法数为
$$n!$$
组合:将$n$个物体分成第$i$组有$n_i$个物体的$m$组，其中组间物体视作不同，组内物体视为相同，方法数为
$$\left(\begin{array}&n\\n_1,n_2,\cdots,n_m\end{array}\right)=\frac{n!}{n_1!n_2!\cdots n_m!}\\
\quad\\
\small当m=2时，简记为
\left(\begin{array}&n\\n_1\end{array}\right)=\left(\begin{array}&n\\n_2\end{array}\right)=\frac{n!}{n_1!n_2!}$$
$\quad\\$
多项式定理
$\quad\\$
倘若$x_1+x_2+\cdots+x_m=n$，则有如下等式成立
$$\small(x_1+x_2+\cdots+x_m)^n=\sum\limits_{n_1+n_2+\cdots+n_m=n}\left(\begin{array}&n\\n_1,n_2,\cdots,n_m\end{array}\right)x_1^{n_1}x_2^{n_2}\cdots x_m^{n_m}$$
$\quad\\$
定和方程的非负整数解个数
$\quad\\$
对于$m$个独立自变量的定和方程$x_1+x_2+\cdots+x_m=n$，将每个自变量加一再分成$m$组，可知其非负整数解的组数为
$$\left(\begin{array}&n+m-1\\m-1\end{array}\right)$$
$\quad\\$
De Morgan Law
$\quad\\$
假设某个试验的样本空间为$S$，其中有一系列事件$E_i，i=1,2,\cdots$，通过对结果不包含于任一事件的不同表述可以得到如下等式
$$\left(\bigcup\limits_{i=1}^{n}E_i\right)^c=\bigcap\limits_{i=1}^{n}E_i^c\qquad\qquad\left(\bigcap\limits_{i=1}^{n}E_i\right)^c=\bigcup\limits_{i=1}^{n}E_i^c$$
$\quad\\$
概率的公理定义
$\quad\\$
假设某个试验的样本空间为$S$，对于其中任意事件$E$，定义一个数$P(E)$，如果它满足如下三条公理，则称其为事件$E$的概率
公理一
$$0\le P(E)\le 1$$
公理二
$$P(S)=1$$
公理三$\qquad$对任意一列互不相容的事件$E_1,E_2,\cdots$(即$\forall i\neq j,E_iE_j=\varnothing$)有
$$P\left(\bigcup\limits_{i=1}^{\infty}E_i\right)=\sum_{i=1}^{\infty}P(E_i)$$
$\quad\\$
容斥恒等式
$\quad\\$
$$P\left(\bigcup\limits_{i=1}^{n}E_i\right)=\\
\quad\\
\sum\limits_{i=1}^n P(E_i)-\sum\limits_{i_1<i_2}P(E_{i_1}E_{i_2})+\cdots+(-1)^{n+1}P(E_1E_2\cdots E_n)$$
$\nabla$证
$$\small 考虑某个独立结果x包含于m个事件中\\\\ \quad\\\\ \small 等式左边x被算了1次\\\\ \quad\\\\ \small 等式右边x被算了\left(\begin{array}&m\\\\1\end{array}\right)-\left(\begin{array}&m\\\\2\end{array}\right)+\cdots+(-1)^{m+1}\left(\begin{array}&m\\\\m\end{array}\right)次\\\\ \quad\\\\ \small 由二项式定理\\\\ \quad\\\\ (1+(-1))^m=\left(\begin{array}&m\\\\0\end{array}\right)-\left(\begin{array}&m\\\\1\end{array}\right)+\left(\begin{array}&m\\\\2\end{array}\right)+\cdots+(-1)^{m}\left(\begin{array}&m\\\\m\end{array}\right)=0\\\\ \quad\\\\ \small每个独立结果在等式两边被计算的次数相等，可知容斥恒等式成立$$
$\nabla$例
YJX是一个不认识英文字母的高中生，现在让他做英语的八选八选词填空，求他全选错的概率
$\nabla$解
$$ \small考虑N选N的情形\\\\ \quad\\\\ \small记YJX选对第i题为事件E_i,则YJX至少选对一题的概率为\\\\ \quad\\\\ P\left(\bigcup\limits_{i=1}^{N}E_i\right)=\\\\ \quad\\\\ \sum\limits_{i=1}^NP(E_i)-\sum\limits_{i_1< i_2}P(E_{i_1}E_{i_2})+\cdots+(-1)^{N+1}P(E_1E_2\cdots E_N)=\\\\ \quad\\\\ \frac{C_N^1(N-1)!}{N!}-\frac{C_N^2(N-2)!}{N!}+\cdots+(-1)^{N+1}\frac{C_N^N(N-N)!}{N!}=\\\\ \quad\\\\ 1-\frac{1}{2!}+\frac{1}{3!}+\cdots+(-1)^{N+1}\frac{1}{N!}\\\\ \quad\\\\ \small故全选错的概率为\\\\ \quad\\\\ P(E_1^cE_2^c\cdots E_N^c)=1-P\left(\bigcup\limits_{i=1}^{N}E_i\right)=\\\\ \quad\\\\ \frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}+\cdots+\frac{(-1)^N}{N!}\\\\ \quad\\\\当N\to\infty时,P\to\frac{1}{e}\approx0.367879\\\\ \quad\\\\ \small通过计算,YJX全选错概率为0.368 $$
$\quad\\$
容斥不等式
$\quad\\$
通过对容斥恒等式右边减项，我们可以得到如下一系列不等式
$$P\left(\bigcup\limits_{i=1}^{n}E_i\right)<\sum\limits_{i=1}^n P(E_i)\\
\quad\\
P\left(\bigcup\limits_{i=1}^{n}E_i\right)>
\sum\limits_{i=1}^n P(E_i)-\sum\limits_{i_1<i_2}P(E_{i_1}E_{i_2})\\
\quad\\
\cdots\\
\quad\\
P\left(\bigcup\limits_{i=1}^{n}E_i\right)<\sum\limits_{r=1}^{2m-1}(-1)^{r+1}\sum\limits_{i_1<i_2<\cdots<i_r}P(E_{i_1}E_{i_2}\cdots E_{i_r})\\
\quad\\
P\left(\bigcup\limits_{i=1}^{n}E_i\right)>\sum\limits_{r=1}^{2m}(-1)^{r+1}\sum\limits_{i_1<i_2<\cdots<i_r}P(E_{i_1}E_{i_2}\cdots E_{i_r})\\
\quad\\
\cdots
$$
$\nabla$证
$$\small 由容斥恒等式的证明，只需说明下列展开式的前k项和为一正一负交替即可\\
\quad\\
(1+(-1))^m=\left(\begin{array}&m\\0\end{array}\right)-\left(\begin{array}&m\\1\end{array}\right)+\left(\begin{array}&m\\2\end{array}\right)+\cdots+(-1)^{m}\left(\begin{array}&m\\m\end{array}\right)=0\\
\quad\\
\small易知\left(\begin{array}&m\\k\end{array}\right)在k\leq \frac{m}{2}时递增，m为奇数时结论显然成立\\
\quad\\
\small m为偶数时在k>\frac{m}{2}时将和看成0减去余项，结论亦成立
$$
$\quad\\$
概率的连续集函数性质
$\quad\\$
称满足$\quad E_1\subset E_2\subset \cdots\subset E_n\subset E_{n+1}\subset\cdots\quad$的事件序列$\{E_n,n\geq 1\}$为递增序列，满足$\quad E_1\supset E_2\supset \cdots\supset E_n\supset E_{n+1}\supset\cdots\quad$的事件序列为递减序列，对递增事件定义新事件$\lim\limits_{n\to\infty}E_n=\bigcup\limits_{i=1}^{\infty}E_i$，对递减事件定义新事件$\lim\limits_{n\to\infty}E_n=\bigcap\limits_{i=1}^{\infty}E_i$，则有
$$\lim\limits_{n\to\infty}P(E_n)=P(\lim\limits_{n\to\infty}E_n)$$
$\nabla$证
$$\small 先证明结论对递增事件成立，直观理解是利用Venn图中一系列互不相交的环\\
\quad\\
\small 构造互不相容的事件F_n(n\geq 1)如下\\
\quad\\
\small F_1=E_1\qquad F_n=E_n(\bigcup\limits_{i=1}^{n-1}E_i)^c=E_nE_{n-1}^c,n>1\\
\quad\\
\small 则有\bigcup\limits_{i=1}^{n}F_i=\bigcup\limits_{i=1}^{n}E_i\qquad\bigcup\limits_{i=1}^{\infty}F_i=\bigcup\limits_{i=1}^{\infty}E_i\\
\quad\\
\begin{aligned}P(\lim\limits_{n\to\infty}E_n)&=P(\bigcup\limits_{i=1}^{\infty}E_i)
=P(\bigcup\limits_{i=1}^{\infty}F_i)\\
\quad\\
&=\sum\limits_{i=1}^{\infty}P(F_i)
=\lim\limits_{n\to\infty}\sum\limits_{i=1}^{n}P(F_i)\\
\quad\\
&=\lim\limits_{n\to\infty}P(\bigcup\limits_{i=1}^{n}F_i)
=\lim\limits_{n\to\infty}P(\bigcup\limits_{i=1}^{n}E_i)\\
\quad\\
&=\lim\limits_{n\to\infty}P(E_n) \end{aligned}\\
\quad\\
\small 接着可由递增序列证明结论对递减序列成立\\
\quad\\
\small 若\{E_n,n\geq 1\}为递减序列，则\{E_n^c,n\geq 1\}为递增序列，于是有\\
\quad\\
\lim\limits_{n\to\infty}P(E_n^c)=P(\bigcup\limits_{i=1}^{\infty}E_i^c)\\
\quad\\
\small由德摩根定律有\\
\quad\\
1-\lim\limits_{n\to\infty}P(E_n)=P((\bigcap\limits_{i=1}^{\infty}E_i)^c)=1-P(\bigcap\limits_{i=1}^{\infty}E_i)\\
\quad\\
\small 即\\
\quad\\
\lim\limits_{n\to\infty}P(E_n)=P(\lim\limits_{n\to\infty}E_n)
$$
$\quad\\$
$\quad\\$
参考与引用来源
$\quad\\$
Sheldon M.Ross概率论基础教程第九版