古典概型

模型与计算公式

最简单的随机现象具有如下两个特征：
1. 在试验中它的全部可能结果只有有限个；
2. 各个事件的发生或者出现是等可能的.
上述类型的随机现象的数学模型称为古典概型.

例如样本空间 $\varOmega = \left\lbrace \omega_1,\omega_2,\cdots,\omega_n \right\rbrace$ ，而且此时应有

\[ P(\omega_1)=P(\omega_2)=\cdots=P(\omega_n)= \frac{1}{n}. \]

因此对于一个事件 $A$ ，由于其总能表示为样本点之和，由事件概率的定义即可得到概率为一个分数.

设 $A = \omega_{i_1}+\cdots+\omega_{i_m}$ ，由事件概率的定义有

\[ P(A) = \frac{m}{n} \]

我们称 $\omega_{i_1},\cdots,\omega_{i_m}$ 为 $A$ 的有利场合，这样就有

定义：概率的古典定义(Laplace, naive definition of probability)

\[P(A) = \frac{有利场合数目}{样本点总数}=\frac{n(A)}{n(\varOmega)}.\]

计数原理

乘法原理和加法原理在此略过.

排列

定义：选排列，全排列

不放回选取中，从 $n$ 个不同的元素中选取 $r$ 个元素进行排列，总数为
$$ A_n^r = \frac{n!}{(n-r)!} $$
特别的，当 $r=n$ 时，称为全排列.

组合

定义：组合

不放回选取中，从 $n$ 个不同元素中取出 $r$ 个元素而不考虑其顺序，称为组合，总数为
$$ \mathrm{C}_n^r = \binom{n}{r} = \frac{A_n^r}{r!} = \frac{n!}{r!(n-r)!} $$

分割

把 $n$ 个不同的元素分为 $k$ 个部分，第一部分 $r_1$ 个，第二部分 $r_2$ 个，……，第 $k$ 部分 $r_k$ 个，则不同的分法有

\[ \frac{n!}{r_1!r_2!\cdots r_k!} \]

上式的数称为多项系数，因为它是展开式 $(x_1+x_2+\cdots+x_k)^n$ 中 $x_1^{r_1}x_2^{r_2}\cdots x_k^{r_k}$ 的系数，当 $k=2$ 的时候即为二项系数，也就是组合.

有重复组合数

当组合的情景变为有放回选取，此时的取法为

\[ \binom{n+r-1}{r} \]

这个数称为有重复组合数.

有重复组合的计算结果可以如何理解？我们现在考虑如下的一个问题：
现在假设 $r=7$ ，我们假设有一个装有 $7$ 个球的盒子，现在我们要插隔板：

这个隔板的含义是什么呢？如果说 $n=3$ ，那么也就有 $3$ 个物品的放回需要记录，此时用 $2$ 个隔板：

这个就表示第一个物品被取了 $2$ 次，第二个物品被取了 $3$ 次，第三个物品被取了 $2$ 次，这样也就是 $7$ 次的取法.

此时对于任意的 $n$ ，我们就需要插入 $n-1$ 个隔板，两个隔板可以插到同一个空隙当中（即没有被取到过），因此对于 $n>r$ 的情形也是同理.

此时有 $r+1$ 个空隙可以插入（两端也算），现在就是说 $n-1$ 个隔板插入 $r+1$ 个空隙当中，因此我们将其视为所有隔板和球总共 $n+r-1$ 个元素的排列，此时从 $n+r-1$ 个位置中决定 $r$ 个球的位置，剩下的隔板位置也就确定了，因此最终的结果也就是

\[ \binom{n+r-1}{r} \]

$\square$

二项式系数公式

根据

\[ (1+x)^n = \sum\limits_{r=0}^n \binom{n}{r}x^r \]

令 $x=1$ 可以得到

\[ 2^n = \sum\limits_{i=1}^n \binom{n}{i} \]

我们利用

\[ (1+x)^a(1+x)^b \]

的运算可以得到

\[ \sum\limits^n_{r=0}\binom{a}{r}\binom{b}{n-r}= \binom{a+b}{n} \]

可以化为实际问题来考虑：在 $a+b$ 个不同的球中不放回地摸出 $n$ 个球，等价于分堆为 $a$ 和 $b$ 个两堆球，对 $a$ 中取 $0$ 个、 $b$ 中取 $n$ 个，……，$a$ 中取 $n$ 个， $b$ 中取 $0$ 个的所有方案的总和.

排列组合的推广

推广为任意实数 $x$ ：

\[ A_x^r = x(x-1)(x-2)\cdots(x-r+1) \]

对于组合就是

\[ \binom{x}{r} = \frac{A_x^r}{r!}. \]

此时的牛顿二项式有

\[ (1+x)^\alpha = \sum\limits_{r=0}^\infty \binom{\alpha}{r}x^r \]

二项分布与超几何分布

二项分布

二项分布对应的是有放回抽样场合，把 $a+b$ 件产品编号，有放回抽 $n$ 次，次品正好出现 $k$ 次的数目是

\[ \binom{n}{k}a^k b^{n-k} \]

因此根据古典概型的公式，有二项分布

\[ b_k = \frac{\displaystyle\binom{n}{k}a^kb^{n-k}}{(a+b)^n} \]

超几何分布

从 $a+b$ 件产品中不放回取出 $n$ 件产品的可能组合全体作为样本点，总数为 $\binom{a+b}{n}$ ，此时取到 $k$ 件次品的概率为

\[ h_k = \frac{\displaystyle \binom{a}{k}\binom{b}{n-k}}{\displaystyle\binom{a+b}{n}} \]

当产品量大，抽样较少的时候，可以用二项分布来近似超几何分布.

概率的基本性质

容斥原理：

\[ n(A\cup B) = n(A)+n(B)-n(AB) \]

当 $A$ 和 $B$ 不相容的时候有

\[ P(A+B) = P(A)+P(B). \]

概率公理

非负性；
规范性：$P(\varOmega)=1$ ；
若事件两两不相容则概率有限可加；

计数原理总结

对于 $n$ 个对象，抽取 $r$ 次的方案数，我们有如下的结果：

顺序与抽样方式	有序	无序
有放回	$n^r$	$\displaystyle\binom{n+r-1}{r}$
无放回	$\dfrac{n!}{r!}$	$\displaystyle\binom{n}{r}$

* 无重复组合数的拓展

（本部分为上课补充）
我们先考虑一个相对简单的问题，找到如下不定方程的所有解的个数：

\[ \begin{cases} y_i \in \mathbb{Z}_+ , & i=1,2,\cdots,n \\ \sum\limits_{i=1}^n y_i = r, &r\geqslant n \end{cases} \]

这个问题使用隔板法更符合直觉，此时相当于 $r$ 个球用 $n-1$ 个挡板造出 $n$ 个空间，第 $i$ 个空间球的个数代表 $y_i$ 的大小. 因此上述的问题答案为 $\displaystyle\binom{r-1}{n-1}$ .

那么无重复组合数实质上就是上述问题的如下变形：

\[ \begin{cases} y_i \in \mathbb{N} , & i=1,2,\cdots,n \\ \sum\limits_{i=1}^n y_i = r, &r\geqslant n \end{cases} \]

现在我们发现刚刚的隔板法就会有一定的问题，问题出在 $y_i$ 取 $0$ 的时候（$0$ 相邻的时候）.

但是这个时候，尤其是在以后的解题过程当中，将这类问题转化为正整数问题是非常简单的做法，我们令 $x_i = y_i +1$ ：

\[ \begin{cases} x_i \in \mathbb{Z}_+ , & i=1,2,\cdots,n \\ \sum\limits_{i=1}^n x_i = r+n, &r\geqslant n \end{cases} \]

此时就回到了原来的问题，因此答案为： $\displaystyle \binom{n+r-1}{n-1}$ .

同理可以解决如下的问题：

\[ \begin{cases}x_i \geqslant-2 ,i=1,2,3,4 \\ x_1+x_2+x_3+x_4 = 2\end{cases} \]

答案为 $\displaystyle \binom{13}{3}$ ，复习的时候不妨一试.

顺序与抽样方式	有序	无序
有放回	\(n^r\)	\(\displaystyle\binom{n+r-1}{r}\)
无放回	\(\dfrac{n!}{r!}\)	\(\displaystyle\binom{n}{r}\)