2.组合分析概要
第 2~4 章讲组合分析
1. 预备知识
定理
- 给定 m 个元素 \(a_1,\dots,a_m\) 及 n 个元素 \(b_1,\dots,b_n\)；从以上两组的每组去除一个元素配成对子 \((a_i,b_j)\)，一共能配成 \(nm\) 个对子
- 多元组：给定 r 组元素，其中第 i 组元素长度为 \(n_i\)；从以上各组中取一个元素配成多元组 \((a_{i_1},b_{i_2},\dots,x_{j_r})\)，一共能配成 \(\prod\limits_{i=1}^rn_i=n_1\cdot n_2\dots n_r\)（例子详见 p 26）
2. 有序样本
有序样本
考虑 n 个元素 \(a_1,\dots,a_n\) 所组成的集合或总体（不分次序）
任何 r 个元素 \(a_{i_1},\dots,a_{i_r}\) 的有序排列，称为从总体中取出的，大小为 r 的一个有序样本
- 有放回的抽样：每个元素的抽取都是在整个总体中进行的，所以同样的元素可以被抽到一次以上，因而在样本的排列中容许有重复的元素；根据 2.1 定理，可能的样本数为 \(n^r\)
- 无放回的抽样：某个元素一旦被抽取，即被从总体中除去，所以在样本的排列中不会有重复元素；样本总数定义为 \((n)_r=\prod\limits_{i=n-r+1}^n i=n(n-1)\dots(n-r+1)\) （\((n)_r=0\)，仅当 \(r>n\)）
注：样本的大小只有相对于给定的总体来说才能确定
阶乘，新记号
阶乘：n 个元素排成不同次序的数目为 \(n!=\prod\limits_{i=1}^n i=n(n-1)\dots1\)
\((n)_r=\frac{n!}{(n-r)!}\) （没有名字？）
特别地，\(n!=1\)，\((n)_0=1\)
随机样本
赋予各个样本相等的概率
练习
- 无放回抽样中，总体中任何一个固定的元素包含在大小为 r 的随机样本中的概率为？
- 有放回抽样中，概率为？
3. 例子
Note
从 n 个元素 \(a_1,\dots,a_n\) 的总体中抽出一个大小为 r 的有放回的随机样本，
“样本中没有重复元素”的事件的概率为 \(p=\frac{(n)_r}{n^r}=\prod\limits_{i=0}^{r-1}\frac{n-i}n=\prod\limits_{i=0}^{r-1}(1-\frac{i}n)\) （仅当 \(r\le n\)）
注：各种排列(样本)都是等可能的
例子：详见p29
- 随机抽样数
- 球与盒子
- 电梯
- 生日悖论（不小于 23 个人当中，不少于 2 个人在同一天生日的概率超过 \(1/2\)）
4. 子总体和分划
总体，子总体
总体：我们用大小为 n 的总体来表示一个由 n 个元素构成的不分次序的集合
（所谓的两个总体不一样，当且仅当 一个总体存在一个元素不属于另一个总体）
子总体：从大小为 n 的总体里选取 r 个元素就构成了一个大小为 r 的子总体；对子总体任意编号可以得到大小为 r 的有序样本，总共有 \(r!\) 种标号方式（即每个子总体可以生成 \(r!\) 种不同的样本），那么大小为 r 的子总体的个数为 \(\frac {(n)_r}{r!}\)
二项式系数
\(\binom nr=\frac{(n)_r}{r!}=\prod\limits_{i=0}^{r-1}\frac{n-i}i=\prod\limits_{i=0}^{r-1}(\frac ni-1)\)
\(\binom nr=\binom n{n-r}\)
特别地 \(\binom n0=1\)
定理
一个包含 n 个元素的总体可以产生 \(\binom nr\) 个不同的含有 r 个元素的子总体（\(r\le n\)）