西电开学考第9题·20种解法(中)

第 9 题。计数题最容易错在「有序还是无序」这一步，而且是静默错。
题目：S = {1, 2, …, 2026}，A、B ⊆ S 且 A ∩ B = ∅。求二元集 {A, B} 的个数。
答案：(3²⁰²⁶ − 1) / 2。
每个元素有三个去处：只进 A、只进 B、都不进 —— 所以是 3²⁰²⁶。
但题目要的是「二元集 {A, B}」，不是有序对 (A, B)，
而 A = B 只在两者都为空时成立，所以恰好要减掉这 1 个再除以 2。
中篇 9 种：
解法八 容斥法 —— 先放开限制，再减掉不合法的
解法九 数学归纳法 —— 严格证明通项公式
解法十 三分类多项式系数 —— 把三态当成多项式的展开系数
解法十一 概率视角法 —— 独立掷三面骰子
解法十二 小 n 枚举法 —— 先把小情形算出来找规律
解法十三 交换对合法 —— A 与 B 的角色可以互换
解法十四 双射核算法 —— 直接构造无序对到整数的双射
解法十五 转移矩阵法 —— 把递推写成矩阵的幂
解法十六 二项式定理法 —— 把 3ⁿ 拆开再重新组合
同一句「求个数」，可以被读成三态分配、可以被读成三进制双射、也可以被读成一次容斥。