阶乘

概述

阶乘是组合数学中的基本函数， $n! = n \times (n - 1) \times \dots \times 1$ ，其渐近行为由 Stirling 近似公式刻画。

定义

阶乘

对于非负整数 $n$ ： $n! = {1 n \cdot (n - 1)! n = 0 n \geq 1$

Stirling 近似： $n! = 2 π n (\frac{n}{e})^{n} (1 + O (\frac{1}{n}))$
更紧凑的界： $2 π n (\frac{n}{e})^{n} e^{1/ (12 n + 1)} \leq n! \leq 2 π n (\frac{n}{e})^{n} e^{1/ (12 n)}$
渐近行为： $ln (n!) = Θ (n ln n)$ ，即 $n!$ 增长快于任何指数函数 $c^{n}$ （ $c$ 为常数）。
阶乘常出现在排列组合、树的结构分析以及算法复杂度分析中。