Let S be a set containing n elements. The number of ordered pairs (A, B) such that A and B are subsets of S and A is a subset of B is ___.

GATE 2021 · Discrete Mathematics · Counting · medium

Answer: 3^n

1. Classify each element into one of three cases: For each element x in S, exactly three membership patterns are compatible with A subseteq B: (x not in A, x not in B), (x not in A, x in B), (x in A, x in B). The fourth case (x in A, x not in B) violates A subseteq B and is excluded.
2. Multiply across all n independent elements: Each of the n elements of S independently contributes a factor of 3. Total pairs = 3 * 3 * ... * 3 (n times) = 3^n.