<p>In how many different ways can a set <em>A</em> of <em>3n</em> elements be partitioned into 3 subsets of equal number of elements? (The subsets <em>P</em>, <em>Q</em>, <em>R</em> form a partition if \(P \cup Q \cup R = A,\ P \cap R = \phi,\ Q \cap R = \phi,\ R \cap P = \phi\).)</p>
Step-by-Step Solution
Key Concept: When partitioning into indistinguishable groups, you must divide by the factorial of the number of groups to eliminate overcounting from their permutations. The total ways to choose 3 groups of n elements each is C(3n,n)·C(2n,n)·C(n,n), but since the 3 subsets are unlabeled (unordered), divide by 3!.
<p><strong>Step 1:</strong> Recognize that we need to partition 3n elements into 3 indistinguishable subsets of n elements each.</p><p><strong>Step 2:</strong> If the subsets were distinguishable (labeled as P, Q, R), we would choose n elements for P from 3n, then n elements for Q from remaining 2n, then remaining n go to R:</p><p>C(3n,n) × C(2n,n) × C(n,n) = $\dfrac{(3n)!}{n!·n!·n!}$</p><p><strong>Step 3:</strong> Since the problem specifies the subsets form a partition (unordered collection), the three subsets are indistinguishable. Any arrangement of the same three groups counts as one partition. We have overcounted by a factor of 3! (the number of ways to arrange 3 subsets).</p><p><strong>Step 4:</strong> Divide by 3! to account for the indistinguishability:</p><p>$\dfrac{(3n)!}{n!·n!·n!·3!} = \dfrac{(3n)!}{6(n!)^3}$</p><p>∴ Answer: $\dfrac{(3n)!}{6(n!)^3}$</p>
Correct Answer: \(\dfrac{(3n)!}{6(n!)^3}\)