排列組合

計數的核心是乘法原理(分步相乘)與加法原理(分類相加)。順序有關用排列 $P(n,r)=\dfrac{n!}{(n-r)!}$,順序無關用組合 $C(n,r)=\dfrac{n!}{r!(n-r)!}$;從 $k$ 類中可重複地取 $n$ 個用重複組合 $H(k,n)=C(n+k-1,n)=C(n+k-1,k-1)$(隔板法);有相同元素的排列要除掉重複 $\dfrac{n!}{p!q!\cdots}$。二項式定理 $(x+c)^n=\sum_{k=0}^{n} C(n,k)x^kc^{n-k}$ 中,$x^kc^{n-k}$ 這一項前面的係數是組合數 $C(n,k)$;若問 $x^k$ 的係數,還要乘上 $c^{n-k}$。

例:5 人排一列甲乙相鄰:綁在一起 $4!\times2=48$;不相鄰 $=120-48=72$。$(x+2)^5$ 的 $x^3$ 係數 $=C(5,3)\cdot2^2=40$。

計數是古典機率的分母與分子,也是密碼學、演算法複雜度與統計分布的基礎。