Question

A is a non-empty set having $n$ elements. P and Q are two subsets of A such that $P \subseteq Q$. Find the number of ways of choosing the subsets P and Q.

• A. $4^n$
• B. $3^n$
• C. $2^n$
• D. $n^2$

Hint:

When counting subset pairs with $P \subseteq Q$, classify elements into “in both”, “only in Q”, and “in none”.

Answer 1

The Correct Option is B

The problem involves finding the number of ways to choose subsets \(P\) and \(Q\) such that \(P \subseteq Q\) from a non-empty set \(A\) with \(n\) elements. For each element in \(A\), there are three possibilities:

• The element is not in \(Q\), and hence also not in \(P\).
• The element is in \(Q\) but not in \(P\).
• The element is in both \(P\) and \(Q\).

As each of the \(n\) elements in \(A\) can independently follow one of these three possibilities, the total number of combinations for subsets \(P\) and \(Q\) is given by taking 3 choices per element of \(A\). Therefore, the number of ways to choose \(P\) and \(Q\) is:

\[3^n\]

Thus, the correct number of ways is \(3^n\).