定义

有限集 $A$：所有满足若干条件的事物的集合。
有限集 $B$：所有满足若干其它条件的事物的集合。

若 $A, B$ 间存在某种对应关系，则求 $A$ 等价于求 $B$。

问题

数量

问题：$|A|$ 是多少？

$|A| = |B|$ 等价于 $A, B$ 间能建立双射。

证明：

1. 若 $|A| = |B|$，将 $A,B$ 中的元素分别编号为 $1,2,\cdots,|A|$，则编号相同的元素可以一一对应，因此 $A,B$ 间可以建立双射。
2. 若 $A, B$ 间能建立双射，假设 $|A| \ne |B|$，不妨设 $|A| > |B|$，则 $A$ 中至少存在一个元素无法在 $B$ 中找到对应，这与 $A,B$ 间能建立双射矛盾，因此假设错误，假设的否命题 $|A| = |B|$ 成立。

例题：

• 130. 火车进出栈问题
• 230. 排列计数

最值

问题：$A$ 上元素某个属性 $P$ 的最值是多少（每个元素有且仅有一个 $P$）？

以最大值为例，若以下条件同时成立，则 $max \lbrace P_a \mid a \in A \rbrace = h(max \lbrace P^\prime_b \mid b \in B \rbrace)$：

1. $\forall a \in A, \exists f, s.t. f(a) \in B$。
2. $\forall b \in B, f^{-1}(b) \in A$。
3. $\forall b \in B, \exists h, s.t. P_{f^{-1}(b)} = h(P^\prime_b)\ 是单增函数$。

注意：$f^{-1}$ 不同于映射的数学定义，可以一对多，且若 $f^{-1}$ 为多值映射，则 $|B| < |A|$ 可能成立。

证明：假设以上条件成立但最值关系式不成立，不妨设 $max \lbrace P_a \mid a \in A \rbrace > h(max \lbrace P^\prime_b \mid b \in B \rbrace)$，则必存在 $P_{a_k} = max \lbrace P_a \mid a \in A \rbrace$，满足 $f(a_k) \notin B$，这与条件 $1$ 矛盾，因此假设错误，假设的否命题成立，即若以上条件成立，则最值关系式成立。其中，$f(a_k) \notin B$ 可反证，假设 $b_k = f(a_k) \in B$，则 $h(max \lbrace P^\prime_b \mid b \in B \rbrace) \ge h(P^\prime_{b_k}) = P_{a_k} = max \lbrace P_a \mid a \in A \rbrace$，这与假设矛盾。

例题：148. 合并果子

存在性

问题：$|A| = 0$ 是否成立？

若以下条件同时成立，则命题 “$|A| = 0$ 等价于 $|B| = 0$” 成立：

1. $\forall a \in A, \exists f, s.t. f(a) \in B$。
2. $\forall b \in B, f^{-1}(b) \in A$。

注意：$f^{-1}$ 不同于映射的数学定义，可以一对多，且若 $f^{-1}$ 为多值映射，则 $|B| < |A|$ 可能成立。

证明：若以上条件成立，则

1. 若 $|A| = 0$，假设 $|B| \ne 0$，则 $\exists b \in B$，满足 $f^{-1}(b) \in A$，因此 $|A| > 0$，这与 $|A| = 0$ 矛盾，因此假设错误，$|B| = 0$ 成立。
2. 若 $|B| = 0$，假设 $|A| \ne 0$，则 $\exists a \in A$，满足 $f(a) \in B$，因此 $|B| > 0$，这与 $|B| = 0$ 矛盾，因此假设错误，$|A| = 0$ 成立。

例题：5380. 三角形

总结

计数问题的等价转换一般要建立双射，最值和存在性问题可以建立从大集合到小集合的映射，从而简化问题。其中，最值问题通常出现原集合中多个元素属性相同，而存在性问题通常是原集合中的多个元素可投影到同一个元素。要证明转换后的问题等价于原问题，即证明原问题的解是目标问题的解，且目标问题的解是原问题的解。

欢迎路过的大佬纠正和补充。