順列・組合せ — 知識ノート

数え上げの基本。

	式	順序	例
順列	$P (n, k) = \frac{n!}{(n - k)!}$	区別する	並べ方
組合せ	$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$	区別しない	選び方

爆発の速さ#

$n!$ の増え方が組合せ最適化の難しさの正体。

Stirling の近似 $n! \approx \sqrt{2 π n} {(n / e)}^{n}$ から、指数よりも速く増えることが分かる。

TSP の経路数 $(n - 1)! / 2$ 、部分集合の数 $2^{n}$ が全探索を不可能にし、ヒューリスティックに頼る理由になっている。

{(x + y)}^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

二項分布の確率質量関数はこの各項。和が 1 になるのは ${((1 - p) + p)}^{n} = 1$ から直ちに従う。