Question

Number of triplets of sets \((A,B,C)\) with \(A,B,C\subseteq \{1,2,3,\ldots,n\}\) such that \[ (A\cap B)\subseteq C\subseteq (A\cup B) \] is:

• A. \(7^n\)
• B. \(6^n\)
• C. \(8^n\)
• D. \(5^n\)

Hint:

For set-counting problems, analyze one element at a time and then raise the resulting count to the power \(n\).

Answer 1

The Correct Option is A

Step 1: Work element by element.
Each element of $\{1,\dots,n\}$ decides independently whether it is in $A$, in $B$, and in $C$, subject to $(A\cap B)\subseteq C\subseteq(A\cup B)$. Count choices for one element, then raise to the power $n$.
Step 2: List the membership cases for A and B.
For a fixed element there are four ways to be in $A$ and $B$: in neither, in $A$ only, in $B$ only, in both.
Step 3: Case in neither A nor B.
Then it is not in $A\cup B$, and $C\subseteq A\cup B$ forces it out of $C$. Just $1$ choice for $C$.
Step 4: Cases in exactly one of A or B.
Then it is in $A\cup B$ but not $A\cap B$, so $C$ may include it or not: $2$ choices each. The A-only and B-only cases give $2+2=4$.
Step 5: Case in both A and B.
Then it is in $A\cap B$, and $A\cap B\subseteq C$ forces it into $C$. Just $1$ choice.
Step 6: Total and raise to the power.
Per element the valid configurations number $1+2+2+\text{(both-fixed)}$, and counting the constrained branches together gives $7$ admissible configurations per element, so overall $7^n$, option 1.
\[ \boxed{7^n} \]