排列组合学习笔记
基本概念
排列：从 $n$ 个不同元素中取出 $m(m \le n)$ 个元素，按照一定的顺序排成一列，叫做从 $n$ 个元素中取出 $m$ 个元素的一个排列。
$$
P_n^m = A_n^m = n(n - 1)(n - 2)\dots(n - m + 1) = \frac{n!}{(m - m)!}
$$
组合：从 $n$ 个不同的元素中，任取 $m(m \le n)$ 个元素为一组，叫做 $n$ 个不同元素中取出 $m$ 个元素的一个组合。
$$
C_n^m = \frac{P_n^m}{p_m} = \frac{n!}{m!(n - m)!}
$$
注意，$C_n^0 = 1$。
二项式定理
其实就是杨辉三角。
$$
(x+y)^n = \binom{n}{0}xny0 + \binom{n}{1}x^{n - 1}y^{1} + \binom{n}{2}x^{n - 2}y^{2} + \dots + \binom{n}{n - 1}x{1}y{n - 1} + \binom{n}{n}x{0}y{n}
$$
在化简下
$$
(x + y)^n = \sum_{k = 0}{n}\binom{n}{k}x{n - k}y^{k} = \sum_{k = 0}{n}\binom{n}{k}x{k}y^{n - k}
$$
一些恒等式
基本恒等式
$$
k \times C_n^k = n \times c_{n - 1}^{k - 1} \\
C_k^n \times C_m^k = C_m^m \times C_{m - n}^{m - k} ; ;;;; (m - k < m - n) \\
\sum_{i = 0}^n C_n^i = 2^n
$$
$(1 + x)^n$ 二项式展开：
$$
\sum_{k = 0}n(-1)k \times C(k, n) = 0 \\
C_n^k + C_n^{k + 1} = C_{n + 1}^{k + 1}
$$
利用杨辉三角
$$
\sum_{k = 0}^{k}C_{n + k}^k = C_{n + m + 1}^{m}
$$
组合应用
求幂和：
$$
\begin{align}
\sum i^2 &= \sum i(i - 1) + \sum i \\
&= 2 \sum C(2, i) + \sum(1, i) \\
&= 2C(3, n + 1) + C(2, n + 1) \\
&= \frac{(n + 1)n(n - 1)}{3} + \frac{(n + 1)n}{2} \\
&= \frac{n(n + 1)(n + 2)}{6}
\end{align}
$$
$$
\begin{align}
\sum i^3 &= \sum (i + 1)i(i - 1) + \sum i \\
&= 6 \sum C(3, i + 1) + \sum(1, i) \\
&= 6C(4, n + 2) + C(2, n + 1) \\
&= \frac{(n + 1)(n + 1)n(n - 1)}{4} + \frac{(n + 1)n}{2} \\
&= [\frac{n(n + 1)}{2}]^2
\end{align}
$$
用二项式定理可以 $\mathcal O (k^2)$ 求 $\sum_{i = 1}^{n} i^k$。
整数划分
要求啥
把一个 $n$ 写成多个大于等于 $1$ 且小于等于其本身的证书的和，则其中各加数所构成的集合为 $n$ 的一个划分。
讲人话就是，将一个正整数 $n$ 分解成多个数相加的和，问你有多少种分法。
例如 $4$ 就有 $5$ 种分法，分别是 $1 + 1 + 1 + 1, 1 + 2 + 1, 1 + 3, 2 + 2, 4$ 这 $5$ 种，注意，自己也算一种。
如何求解
人话讲解：
我们想象下，就是我们要分解 $n$ 这个数字，相当于我们有 $n$ 个一模一样的小球，然后我们往里面放隔板，我们隔板隔开的就是分解出的一个数字，由于我们是对 $n$ 个小球放隔板，所以其总和是不会变化的。
但是，由于这些小球都是一样的，也就是我们不考虑顺序，所以我们就需要使用排列组合中的 $C$ 排列。
数学讲解：
令 $n$ 为需要划分的整数，$m$ 为划分后的最大整数，有：
$$
f(n, m) =
\begin{cases}
1, (n = 1 ; or ; n = 0) \\
1, (m = 1) \\
f(n, n), (m > n) \\
f(n, m - 1) + f(n - m, m), (m \le n)
\end{cases}
$$
其中 $f(n, n)$ 就为 $n$ 的划分数。
集合划分
求解啥
求解将 $n$ 个不同的元素拆分成 $m$ 个集合（非空集）的方案数。
如何求解？
记 $S(n, m)$ 为方案数，有：
$$
\begin{cases}
S(n, 0) = 0, (m = 0) \\
S(n, 1) = 1, (m = 1) \\
S(n, n) = 1 \\
S(n, k) = 0, (k > n) \\
S(n, m) = m \times S(n - 1, m) + S(n - 1, m - 1), (1 < m < n)
\end{cases}
$$
这类数也称为第二类 Stirling 数。
卡特兰数
卡特兰数（Catalan number）是一个常出现在各种计数问题种的数列。
前几项为：$1, 1, 2, 5, 14, 132, \dots$。
例如：求 $n$ 对相同括号的括号序列数，$n$ 个数顺序进栈的出栈序列总数，有 $n$ 条边的凸多边形的三角划分数，由 $n + 1$ 个节点组成的二叉搜索树的数量等等问题都可以用卡特兰数来解决。
卡特兰数 $C_{n + 1}$ 满足递推式：
$$
C_{n + 1} = C_0C_n + C_1C_{n - 1} + \dots + C_nC_0
$$
卡特兰数的通项公式：$C_n = \frac{C_{2n}^n}{n + 1}$
练习习题
代码源：P1106
代码源：P1107（洛谷 P2532）