Browse · MathNet
PrintAPMO
counting and probability
Problem
Let be the set of all -tuples where each , is a subset of . Let denote the number of elements of the set . Find the number
Solution
Let be a subset of the set and let . Then the set can be obtained as the union of sets in different ways since each element can belong to nonempty families of subsets .
Thus we have
Thus we have
Final answer
1998 (2^n − 1) 2^{1997 n}
Techniques
Counting two waysAlgebraic properties of binomial coefficients