Skip to main content
OlympiadHQ

Browse · MathNet

Print

APMO

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

Final answer
1998 (2^n − 1) 2^{1997 n}

Techniques

Counting two waysAlgebraic properties of binomial coefficients