MathLabs

第1题

设 S\mathcal S 为所有 nn 元组 (A1,A2,…,An)(A_1,A_2,\ldots,A_n) 的集合，其中每个 AiA_i 是 {1,2,…,1998}\{1,2,\ldots,1998\} 的子集。对 K∈SK\in\mathcal S，令 f(K)=∣A1∪A2∪⋯∪An∣f(K)=|A_1\cup A_2\cup\cdots\cup A_n|。求 ∑K∈Sf(K)\sum_{K\in\mathcal S}f(K)。
第 2/5 步：建立递推式
上一步下一步
s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)s(n,m)=2^ns(n,m-1)+(2^n-1)2^{n(m-1)}
详细分析

对 {1,…,m−1}\{1,\ldots,m-1\} 上的元组，独立选择 mm 是否属于每个 AiA_i，得到 2n2^n 个扩展。原并集贡献乘以 2n2^n；除一个外其余都含 mm，贡献第二项。因此 s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)s(n,m)=2^ns(n,m-1)+(2^n-1)2^{n(m-1)}。