分治递推

组合数学中最常见的思想是分治：把一个规模为 $n$ 的对象，按某个天然位置拆成较小的同类对象。

若一个对象只能落入若干互不重叠的情况，使用加法：

$$
T(n)=T_1(n)+T_2(n)+\cdots
$$

若一个对象由几个互相独立的部分共同组成，使用乘法：

$$
T(n)=A(n)\cdot B(n)
$$

很多递推式混合使用两者。

Info
递推式里最容易漏的是空结构。 空结构有时表示 `0`，有时表示 `1`： > - 若计数的是“方案数”，空方案通常算 `1` 种。 > - 若计数的是“结点数”，空树通常有 `0` 个结点。

对应转化

如果某类对象不好直接计数，可以把它转化为另一类更容易计数的对象。转化必须满足：

  1. 每个原对象都能映射到一个新对象。
  2. 不同原对象不能映射成同一个新对象。
  3. 每个新对象都能还原回一个合法原对象。
  4. 原题的限制条件在转化后仍然被保留。

也就是要建立可逆的一一对应。

补集与反面计数

当正面计数复杂时，可以考虑从总数中减去非法情况：

$$
\text{合法数}=\text{总数}-\text{非法数}
$$

这种方法适合非法情况更容易描述的题。使用时要注意非法情况是否互相重叠；若重叠，就不能简单相加，需要进一步分类或使用容斥思想。