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) を求めよ。
ステップ 3/5: 初期値を定める
前のステップ次のステップ
s(n,1)=2n−1s(n,1)=2^n-1
詳しい解説

m=1m=1 では nn 個の集合の少なくとも一つが 11 を含むときだけ和の大きさが 11 になる。従って s(n,1)=2n−1s(n,1)=2^n-1。