西电开学考第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。
下篇 4 种：
解法十七 组合恒等式法 —— 用已知恒等式一步到位
解法十八 空集分项法 —— 把 A = ∅ 和 B = ∅ 的情形单独处理
解法十九 精确大数验证 —— 用 Python 大整数核对位数与末位
解法二十 独立公式复算 —— 换一条完全不同的路再算一次
同一句「求个数」，可以被读成三态分配、可以被读成三进制双射、也可以被读成一次容斥。