数学

HeChuangJun约 1492 字大约 5 分钟

排列

从n个不同元素中取出(m<=n)个元素所有排列的个数，按照一定顺序排列成一列，叫做从n个不同元素中取出m(m<=n)个元素的排列数（number of arrangement），用符号 $A_{n}^{m}$ 表示。
根据分布乘法计数原理可得排列数公式

A_{n}^{m} = n (n - 1) (n - 2) \cdot \cdot \cdot (n - m + 1) = \frac{n (n - 1) (n - 2) \cdot \cdot \cdot 2 \cdot 1}{(n - m) (n - m - 1) \cdot \cdot \cdot 2 \cdot 1} = \frac{n!}{(n - m)!}

证明：求排列数 $A_{n}^{m}$ 可以按依次填m个空位来考虑：假定有排好顺序的m个空位,从n个不同元素a1,a2,a3,…,an中任意取m个去填空,一个空位填1个元素，每一种填法就对应1个排列，因此，所有不同填法的种数就是排列数。填空可分为m个步骤：
- 第1步，第1位可以从n个元素中任选一个填上，共有n种填法；
- 第2步，第2位只能从余下的n-1个元素中任选一个填上，共有n-1种填法；
- 第3步，第3位只能从余下的n-2个元素中任选一个填上，共有n-2种填法；
- ……
- 第m步，当前面的m-1个空位都填上后，第m位只能从余下的n-(m-1)个元素中任选一个填上，共有n-m+1种填法。
- 根据分步计数原理，全部填满m个空位共有n(n-1)(n-2)…(n-m+1)种填法

组合

组合公式的推导是由排列公式去掉重复的部分而来的,组合无序，排列有序
从n个不同元素中取出(m<=n)个元素所有组合的个数，叫做从n个不同元素中取出m(m<=n)个元素的组合数（number of combination），用符号 $C_{n}^{m}$ 表示。或者欧美记为 $(\begin{matrix} n \\ m \end{matrix})$

C_{n}^{m} = \frac{A_{n}^{m}!}{A_{m}^{m}!} = \frac{n (n - 1) (n - 2) \cdot \cdot \cdot (n - m + 1)}{m (m - 1) \cdot \cdot \cdot 1} == \frac{n (n - 1) (n - 2) \cdot \cdot \cdot (n - m + 1) \cdot (n - m)!}{m (m - 1) \cdot \cdot \cdot 1 \cdot (n - m)!} \frac{n!}{m! (n - m)!}

推导：利用排列组合关系推导,将排列问题 $A_{n}^{m}$ 分为2步：第1步，从n个元素中抽取m个，无序，就是组合问题 $C_{n}^{m}$ ;第2步，对m排序 $A_{m}^{m}$ ，根据乘法原理得到

A_{n}^{m} = C_{n}^{m} A_{m}^{m}

m用n-(n-m)代替得到性质1-互补

C_{n}^{m} = \frac{n!}{(n - m)! [n - (n - m)]!} = C_{n}^{n - m}

当总元素个数从n变为n+1时，可分为不包含新元素的组合和包含新元素的组合，由分类加法计数原理，可得组合的性质2-组合恒等式

C_{n + 1}^{m} = C_{n}^{m} + C_{n}^{m - 1}

证明

C_{n}^{m} + C_{n}^{m - 1} = \frac{n!}{m! (n - m)!} + \frac{n!}{(m - 1)! (n - m + 1)!} = \frac{n! (n - m + 1)! + n! \cdot m}{m! (n - m + 1)!} = \frac{n! [(n - m + 1) + m]}{m! (n - m + 1)!} = \frac{[(n + 1)!]}{m! (n - m + 1)!} = C_{n + 1}^{m}

二项式定理

二项式展开公式为

(a + b)^{n} = \sum_{i = 0}^{n} C_{n}^{i} a^{i} b^{n - i} (n 为 正 整 数)

其中组合 $C_{n}^{i}$ 定义为

C_{n}^{i} = \frac{n (n - 1) \cdot \cdot \cdot (n - i + 1)}{i!} = \frac{n!}{i! (n - i)!}

证明：若展开多项式的时候先不合并同类项（每项前面的系数都是 1）则若不合并相同项
$(a + b)^{0} = 1$ 有1项
$(a + b)^{1} = a + b$ 有2项
$(a + b)^{2} = a a + a b + b a + b b$ 有4项
$(a + b)^{3} = a a a + a a b + a b a + a b b + b a a + b a b + b b a + b b b$ 有8项
$(a+b)^n $有 $2^{n}$ 项
相当于用a和b填满n个有序的位置，每个位置都可以取a或b，共有 $2^{n}$ 种排列，每种排列就是一项，所以共有 $2^{n}$ 项（不合并相同项）。把 $2^{n}$ 项中相同项进行合并，把其中出现了i个a及n-i个b的项都记为 $a^{i} b^{n - i}$ ，那么共有 $c_{n}^{i}$ 个这样的项。把它们相加得 $C_{n}^{i} a^{i} b^{n - i}$ 。所以

(a + b)^{n} = \sum_{i = 0}^{n} C_{n}^{i} a^{i} b^{n - i}

伯努利实验

若随机试验E只有2个可能的结果：A与 $\overset{―}{A}$ 则称E为伯努利试验（Bernoulli trial）。若将E独立重复进行n次，则称n重伯努利试验。
伯努利试验中的2个结果A与 $\overset{―}{A}$ 也被称为 “成功” 与 “失败”。所以当用数字1和0来表示的时候，这个数字被称为第n个试验的成功次数。即对n重伯努利试验，其成功次数X等于每个试验的成功次数之和,其中， $x_{i}$ 为第
次试验的成功次数。

X = \sum_{i} x_{i}

二项分布

如果记X为n重伯努利试验中成功（记为事件A）的次数，则X的可能取值为0,1..,n。记p为每次试验中A发生的概率，即P(A)=p，则P( $\overset{―}{A}$ ) =1-p,n重伯努利试验的基本结果可以记作 $ω = (ω_{1}, ω_{2}, . ., ω_{n})$ 其中 $ω_{i}$ 为A或者为 $\overset{―}{A}$ ,这样的 $ω_{i}$ 共有 $2^{n}$ 个，组成了样本空间 $Ω$
下面求事件X的分布列，即{X=k}的概率。若某个样本点 $ω = (ω_{1}, ω_{2}, . ., ω_{n}) \in {x = K}$ 意味着 $ω_{1}, ω_{2}, . ., ω_{n}$ 中有k个A,n-k个 $\overset{―}{A}$ ,由事件的独立性知：

P (ω) = p^{k} (1 - p)^{n - k}

而事件{X=k}中这样的 $ω$ 共有个 $(\begin{matrix} n \\ k \end{matrix})$ ，所以X的分布列为：

P (X) = (\begin{matrix} n \\ k \end{matrix}) p^{k} (1 - p)^{n - k} 其 中 (k = 0, 1, . ., n)

这个分布称为二项分布（binomial distribution），记为 X~b(n,p)
根据二项式定理有

X = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) p^{k} (1 - p)^{n - k} = [p + (1 - p)]^{n} = 1

并且从上式可以看出，二项概率 $(\begin{matrix} n \\ k \end{matrix}) p^{k} (1 - p)^{n - k}$ 恰好是二项式 $[p + (1 - p)]^{n}$ 的展开式中的第k+1项，这正是其名称的由来。二项概率是一种离散分布