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) を求めよ。
ステップ 4/5: 漸化式を解く
前のステップ次のステップ
s(n,m)=m(2nm−2n(m−1))s(n,m)=m\left(2^{nm}-2^{n(m-1)}\right)
詳しい解説

漸化式と初期値を用いて mm に関する帰納法を行うと、s(n,m)=m(2nm−2n(m−1))s(n,m)=m(2^{nm}-2^{n(m-1)})。