MathLabs

第1問

S\mathcal S を、各 AiA_i が {1,2,…,1998}\{1,2,\ldots,1998\} の部分集合である全ての nn 組 (A1,A2,…,An)(A_1,A_2,\ldots,A_n) の集合とする。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) を求めよ。
ステップ 1/5: 有限底集合での和を定義する
前のステップ次のステップ
s(n,m)=∑K∣A1∪⋯∪An∣s(n,m)=\sum_{K}|A_1\cup\cdots\cup A_n|
詳しい解説

全ての AiA_i が {1,2,…,m}\{1,2,\ldots,m\} の部分集合である場合の求める和を s(n,m)s(n,m) と置く。この小さい問題には 2mn2^{mn} 個の組がある。