A First Course In Probability
发表于 2025-06-15
概率论基础教程
1. 组合分析
1.2 计数基本法则
- 计数基本法则
假设有两个实验，其中实验1有m种可能的结果，对于实验1的每一种结果，实验2有n种可能的结果，则这两个实验一共有mn种可能的结果。
- 推广的计数基本法则
如果一共有r个实验，其中实验1有 \(n_1\) 种可能的结果，对于实验1的每一种结果，实验2有 \(n_2\) 种可能的结果，对应于前两个实验的每一种可能的结果，实验3有 \(n_3\) 种可能的结果 ……那么这r个实验一共有 \(n_1\) \(n_2\) … \(n_r\) 种可能的结果。
1.3 排列
- 假设有n个元素，可知一共有
种不同的排列方式。
\[n! = 1 \times 2 \times ... \times n, 同时定义 0! = 1\]- 假设有n个元素，如果其中 \(n_1\) 个元素彼此相同，另 \(n_2\) 个元素彼此相同，…, \(n_r\) 个元素彼此相，那么一共有
种不同的排列方式。
1.4 组合
- 对于 \(r \leq n\)，我们定义 \(\binom{n}{r}\) 如下：
这样 \(\binom{n}{r}\) 就表示从 \(n\) 个元素中一次取 \(r\) 个的可能组合个数。⊖
⊖ 按照惯例，定义 \(0! = 1\)，因此， \(\binom {n} {0} = \binom {n} {n} = 1\) 。
当 \(i < 0\) 或者 \(i > n\) 时，我们也认为 \(\binom {n} {i} = 0\) 。
- 以下是一个非常有用的组合恒等式：
二项式定理
\[(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}\]下面将介绍二项式定理的两种证明方法，其一是数学归纳法，其二是基于组合考虑的证明。
二项式定理的归纳法证明
当 \(n = 1\) 时，上式 可化为：
\[x + y = \binom{1}{0} x^0 y^1 + \binom{1}{1} x^1 y^0 = y + x\]假设式 (4.2) 对于 $n - 1$ 成立，那么对于 $n$，
\[(x + y)^n = (x + y)(x + y)^{n - 1} = (x + y) \sum_{k=0}^{n-1} \binom{n - 1}{k} x^k y^{n - 1 - k}\]乘法展开：
\[= \sum_{k=0}^{n - 1} \binom{n - 1}{k} x^{k+1} y^{n - 1 - k} + \sum_{k=0}^{n - 1} \binom{n - 1}{k} x^k y^{n - k}\]将前面的求和公式中令 $i = k + 1$，后面的求和公式中令 $i = k$，则有：
\[(x + y)^n = \sum_{i=1}^n \binom{n - 1}{i - 1} x^i y^{n - i} + \sum_{i=0}^{n - 1} \binom{n - 1}{i} x^i y^{n - i}\]合并：
\[= x^n + \sum_{i=1}^{n - 1} \left[ \binom{n - 1}{i - 1} + \binom{n - 1}{i} \right] x^i y^{n - i} + y^n\]根据组合恒等式：
\[= \sum_{i=0}^n \binom{n}{i} x^i y^{n - i}\]- 记号
如果 \(n_1 + n_2 + \cdots + n_r = n\)，则定义
\[\binom{n}{n_1, n_2, \dots, n_r} = \frac{n!}{n_1! \, n_2! \cdots n_r!}\]因此， \(\binom{n}{n_1, n_2, \dots, n_r}\) 表示把 \(n\) 个不同的元素分成大小分别为 \(n_1, n_2, \dots, n_r\) 的 \(r\) 个不同组的组合数。
多项式定理
\[(x_1 + x_2 + \cdots + x_r)^n = \sum_{\substack{(n_1, \dots, n_r) \\ n_1 + \cdots + n_r = n}} \binom{n}{n_1, n_2, \dots, n_r} x_1^{n_1} x_2^{n_2} \cdots x_r^{n_r}\]上述的求和号是对满足 \(n_1 + n_2 + \cdots + n_r = n\) 的所有非负整数向量 \((n_1, n_2, \dots, n_r)\) 求和。
本文访问次数：... 次