Permutations & Combinations
Partitions of Sets
Grade 11
Question:
<p>The set \(S = \{1, 2, 3, \ldots, 12\}\) is to be partitioned into three sets \(A, B, C\) of equal size. Thus, \(A \cup B \cup C = S\), \(A \cap B = B \cap C = A \cap C = \varnothing\). The number of ways to partition \(S\) is</p>
<p>(a) \(\frac{12!}{3!(4!)^3}\)</p>
<p>(b) \(\frac{12!}{3!(3!)^4}\)</p>
<p>(c) \(\frac{12!}{(4!)^3}\)</p>
<p>(d) \(\frac{12!}{(3!)^4}\)</p>
Step-by-Step Solution
Key Concept: Use multinomial coefficient for partitioning, then divide by the number of ways to arrange the identical groups since set labels don't matter in a partition.
<p>We need to partition 12 elements into three groups of 4 elements each.</p><p>Number of ways to choose 4 elements for set A from 12: $\binom{12}{4}$</p><p>Number of ways to choose 4 elements for set B from remaining 8: $\binom{8}{4}$</p><p>Number of ways to choose 4 elements for set C from remaining 4: $\binom{4}{4} = 1$</p><p>Total = $\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = \frac{12!}{4!8!} \times \frac{8!}{4!4!} \times 1 = \frac{12!}{(4!)^3}$</p><p>Since the three sets A, B, C are indistinguishable (order doesn't matter), we divide by $3!$:</p><p>Answer = $\frac{12!}{3!(4!)^3}$</p><p>∴ Answer is (a).</p>
Correct Answer: A