S is the set of all possible n-tuples (X1, X2, ... , Xn) where each Xi is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.
Solution
Answer: 1998(21998n - 21997n).
Let s(n, m) be the sum where each Xi is a subset of {1, 2, ... , m}. There are 2m possible Xi and hence 2mn possible n-tuples. We have s(n, m) = 2ns(n, m-1) + (2n - 1)2n(m-1) (*). For given any n-tuple {X1, ... , Xn} of subsets of {1, 2, ... , m-1} we can choose to add m or not (2 choices) to each Xi. So we derive 2n n-tuples of subsets of {1, 2, ... , m}. All but 1 of these have f(k) incremented by 1. The first term in (*) gives the sum for m-1 over the increased number of terms and the second term gives the increments to the f(k) due to the additional element.
Evidently s(n, 1) = 2n - 1. It is now an easy induction to show that s(n, m) = m(2nm - 2n(m-1)).
Putting m = 1998 we get that the required sum is 1998(21998n - 21997n).
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002