MathLabs

Problem 1

Let S\mathcal S be the set of all nn-tuples (A1,A2,…,An)(A_1,A_2,\ldots,A_n) in which each AiA_i is a subset of {1,2,…,1998}\{1,2,\ldots,1998\}. For K∈SK\in\mathcal S, let f(K)=∣A1∪A2∪⋯∪An∣f(K)=|A_1\cup A_2\cup\cdots\cup A_n|. Find ∑K∈Sf(K)\sum_{K\in\mathcal S}f(K).
Step 1 of 5: Define the finite-ground-set sum
Previous stepNext step
s(n,m)=∑K∣A1∪⋯∪An∣s(n,m)=\sum_{K}|A_1\cup\cdots\cup A_n|
Detailed analysis

Let s(n,m)s(n,m) denote the required sum when every AiA_i is a subset of {1,2,…,m}\{1,2,\ldots,m\}. There are 2mn2^{mn} tuples in this smaller problem.