西电开学考第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。
上篇 7 种：
解法一 三态分配法 —— 每个元素有三种去向，这是全题的发动机
解法二 排除退化项 —— 唯一的坏蛋是 A = B = ∅
解法三 按 |A∪B| 分类求和 —— 先定并集大小，再分配
解法四 按 A 的大小分类 —— 先定 A，再数 B 有多少种
解法五 三进制双射法 —— 把每一对编码成一个三进制串
解法六 递推法 —— 加一个元素，数目怎么变
解法七 生成函数法 —— 把计数压成幂级数
同一句「求个数」，可以被读成三态分配、可以被读成三进制双射、也可以被读成一次容斥。