一些常用的定理&公式

$\circ$ 这里，我们定义 $0^0 = 1, 0! = 1$ (当然，这么做的意义是让下文中提到的排列数和组合数的阶乘公式在 $k = 0$ 时仍然成立，以及使二项式定理在$a = 0$ 或 $b = 0$ 时仍然成立) $\circ$ 排列数 $A(n,k)$（也写作 $A_n^k$）的意义为从 $n$ 个元素的集合 $S$ 中，取出 $m$ 个元素组成**有序**排列的个数。 其公式为： $$A(n, k) = \frac {n!} {(n - k)!} \text{ 其中 $k \le n$,特别的,}A(n,0) = 1$$ $\circ$ 组合数 $C(n,k)$（也写作 $C_n^k$）的意义为从 $n$ 个元素的集合 $S$ 中，**无序**选取出 $k$ 个元素的方案数。 其公式为： $$C(n,k) = \frac {n!} {k! \times (n-k)!} \text{ 其中}k \leq n ,\text{特别的},C(n,0) = 1$$ $\circ$ 组合恒等式：$C_n^m = C_n^{n - m},C_{n}^m = C_{n - 1}^m + C_{n - 1}^{m - 1}$ $\circ$ 二项式定理：$(a + b)^n = \sum\limits_{k = 0}^{n}\dbinom{n}{k}a^{n - k}b^k$ 其中 $\dbinom{n}{k}$ 为二项式系数，其等于 $C_n^k$ 。 $\circ$ $\sum_{i = 0}^n \limits \dbinom{n} {i} = 2^n,\sum_{i = 0}^{n} \limits \dbinom{n} {i} \times i = n2^{n - 1}$ $\circ$ 艾佛森括号 $[P]$ (其中 $P$ 为一个逻辑表达式，更广泛的来说，是一个可真可假的命题)，它是一种方括号记号，如果方括号内的条件满足则为 1，不满足则为 0。 更确切的讲： $$[P] = \begin{cases} 1 & \text{If $P$ is true;} \\ 0 & \text{Otherwise}\end{cases}$$ $\circ$ 上下取整转化：$\lceil \frac {n} {m} \rceil = \lfloor \frac {n - 1} {m} \rfloor + 1 = \lfloor \frac {n + m - 1} {m} \rfloor$ 。 设 $n = mk + r\,(k,r \in Z, 0 \le r < m)$： 当 $r > 0$ 时： $$\lceil \frac {n} {m} \rceil = \lceil \frac {mk + r} {m} \rceil = \lceil k + \frac {r} {m} \rceil = k + \lceil \frac {r} {m} \rceil = k + 1$$ $$\lfloor \frac {n - 1} {m} \rfloor + 1 = \lfloor \frac {mk + r - 1} {m} \rfloor + 1 = \lfloor k + \frac {r - 1} {m} \rfloor + 1 = k + 1 + \lfloor \frac {r - 1} {m} \rfloor = k + 1$$ 当 $r = 0$ 时： $$\lceil \frac {n} {m} \rceil = \lceil \frac {mk} {m} \rceil = k$$ $$\lfloor \frac {n - 1} {m} \rfloor + 1 = \lfloor \frac {mk - 1} {m} \rfloor + 1 = \lfloor k - \frac {1} {m} \rfloor + 1 = k - 1 + 1 = k$$ 故：$\lceil \frac {n} {m} \rceil = \lfloor \frac {n - 1} {m} \rfloor + 1$ 。 而 $\lfloor \frac {n - 1} {m} \rfloor + 1 = \lfloor \frac {n - 1} {m} \rfloor + \frac {m} {m} = \lfloor \frac {n - 1} {m} + \frac {m} {m} \rfloor = \lfloor \frac {n + m - 1} {m} \rfloor$，故 $\lceil \frac {n} {m} \rceil = \lfloor \frac {n + m - 1} {m} \rfloor$ 。