統計學/機率論/組合學

組合學研究從樣本空間中選擇的物體的排列和組合。對統計學有良好掌握需要預先了解組合學。

計數原理

計數原理類似於乘法原理。如果一個過程包含$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}$

這使我們能夠構建帕斯卡三角形，這對於確定組合很有用