Permutations & Combinations
Subsets
Grade 11
Question:
<p><i>A</i> is a set containing <i>n</i> elements. A subset \(P_1\) of <i>A</i> is chosen. The set <i>A</i> is reconstructed by replacing the elements of \(P_1\). Next, a subset \(P_2\) of <i>A</i> is chosen and again the set is reconstructed by replacing the elements of \(P_2\). In this way, <i>m</i> (>1) subsets \(P_1, P_2, \ldots, P_m\) of <i>A</i> are chosen. The number of ways of choosing \(P_1, P_2, \ldots, P_m\) is</p>
<p>\((2^m - 1)^n\) if \(P_1 \cap P_2 \cap \cdots \cap P_m = \phi\)</p>
<p>\(2^{mn}\) if \(P_1 \cup P_2 \cup \cdots \cup P_m = A\)</p>
<p>\(3^{mn}\) if \(P_1 \cap P_2 \cap \cdots \cap P_m = \phi\)</p>
<p>\((2^m - 1)^n\) if \(P_1 \cup P_2 \cup \cdots \cup P_m = A\)</p>
Step-by-Step Solution
Key Concept: Each element of A can independently either belong or not belong to each of the m subsets. Since there are n elements and each has 2 choices for each of m subsets, use the multiplication principle to get the total count.
<p><strong>Step 1:</strong> For each element in set A, we need to decide independently whether it belongs to subset P₁, P₂, ..., or Pₘ.</p><p><strong>Step 2:</strong> For each element x ∈ A, when choosing the m subsets sequentially with replacement:</p><ul><li>For P₁: element x is either in P₁ or not (2 choices)</li><li>For P₂: element x is either in P₂ or not (2 choices, independent of P₁)</li><li>For Pₘ: element x is either in Pₘ or not (2 choices, independent of previous choices)</li></ul><p><strong>Step 3:</strong> For one element, there are 2^m ways to form its membership pattern across all m subsets.</p><p><strong>Step 4:</strong> Since all n elements make independent choices, the total number of ways = (2^m)^n = <strong>2^(mn)</strong></p><p><strong>Alternatively:</strong> Each subset Pᵢ can be any of the 2^n possible subsets of A. Since we choose m subsets independently with replacement, total ways = (2^n)^m = 2^(mn)</p><p>∴ Answer: <strong>2^(mn)</strong> or <strong>4^(n(m-1)/2)</strong> depending on option format (typically option D)</p>
Correct Answer: D