统计学/概率论/组合学

组合学研究从样本空间中选择的物体的排列和组合。对统计学有良好掌握需要预先了解组合学。

计数原理

计数原理类似于乘法原理。如果一个过程包含$n$个步骤，并且第 $i$ 个步骤可以以 $x_{i}$ 种方式完成，那么整个过程可以以 $x_{1}\times x_{2}\times ...\times x_{n}$ 种不同的方式完成。

排列

排列是集合中 $n$ 个元素的不同排列。根据计数原理，集合中 $n$ 个对象的排列方式有 $n\times (n-1)\times (n-2)\times ...\times 1=n!$ 种。如果其中一些元素不唯一呢？那么，如果有 $k$ 种不同类型的元素，那么可能的排列总数为 ${\frac {n!}{n_{1}!\times n_{2}!\times ...\times n_{k}!}}$。如果我们将元素排列在圆圈中，而不是直线上呢？那么排列的数量为 $(n-1)!$。

当遇到非常大的阶乘时，一个有用的近似值是斯特林公式：$n!\approx {\sqrt {2\pi n}}({\frac {n}{e}})^{n}$

现在假设我们只从集合中选择r个不同的元素（不重复）。那么可能的排列数量变为 ${\frac {n!}{(n-r)!}}=_{n}P_{r}$。

组合

组合本质上是一个子集。它类似于排列，只是不考虑顺序。假设我们有一个包含 $n$ 个元素的集合，并取 $r$ 个元素。可能的组合数量为 ${\frac {_{n}P_{r}}{r!}}={\frac {n!}{r!\times (n-r)!}}=_{n}C_{r}=\displaystyle {n \choose r}$。

另请注意 $\sum _{r=0}^{k}\displaystyle {m \choose r}\times \displaystyle {n \choose k-r}=\displaystyle {m+n \choose k}$

组合在二项式展开中很常见。考虑以下二项式展开

$(x+y)^{1}=x+y$

$(x+y)^{2}=x^{2}+2xy+y^{2}$

$(x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}$

$(x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{1}+4xy^{2}+y^{3}$

正如您从上面可能注意到的，对于任何正整数 $n$，$(x+y)^{n}=\sum _{i=0}^{n}[\displaystyle {n \choose r}\times x^{n-r}\times y^{r}]$

从上面另一个观察结果被称为帕斯卡定律。它指出 $\displaystyle {n \choose r}=\displaystyle {n-1 \choose r}+\displaystyle {n-1 \choose r-1}$

这使我们能够构建帕斯卡三角形，这对于确定组合很有用