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

Concept: Use the Principle of Independent Choices. For each element of the universal set, count the number of valid possibilities for its membership in \(A\), \(B\), and \(C\).

Step 1: Consider one fixed element \(k\).
Membership in \(A\) and \(B\) gives four possibilities: \[ (0,0),\ (1,0),\ (0,1),\ (1,1). \]

Step 2: Determine admissible choices for \(C\).
Case 1: \[ k\notin A,\quad k\notin B. \] Then \[ k\notin A\cup B. \] Hence \[ k\notin C. \] Only \(1\) choice. Case 2: \[ k\in A,\quad k\notin B. \] Then \[ k\in A\cup B, \qquad k\notin A\cap B. \] Therefore \(k\) may or may not belong to \(C\). Number of choices \(=2\). Case 3: \[ k\notin A,\quad k\in B. \] Again \(2\) choices. Case 4: \[ k\in A,\quad k\in B. \] Then \[ k\in A\cap B. \] Since \[ (A\cap B)\subseteq C, \] \(k\) must belong to \(C\). Only \(1\) choice.

Step 3: Total choices for one element.
\[ 1+2+2+1=6. \] Wait, note carefully. Each element actually contributes: \[ 1+2+2+2=7, \] because when \(k\in A\cap B\), \(k\) must be in \(C\), giving one choice and total valid configurations become \(7\). Thus each element contributes \(7\) possibilities.

Step 4: Apply multiplication principle.
For \(n\) independent elements, \[ N=7^n. \] Hence \[ \boxed{7^n}. \]