Permutations & Combinations
Combinations
Grade 11
Question:
<p>Out of \(2n\) places we just have to choose \(n\) places for boys and at the remaining places we arrange girls. This can be done in \({}^{2n}C_n\) ways. Also \(({}^nC_0)^2 + ({}^nC_1)^2 + \ldots + ({}^nC_n)^2 = {}^{2n}C_n\). Which of the following are correct?</p>
<p>(a) The number of ways to arrange \(n\) boys and \(n\) girls in \(2n\) places is \({}^{2n}C_n\)</p>
<p>(b) \(({}^nC_0)^2 + ({}^nC_1)^2 + \ldots + ({}^nC_n)^2 = {}^{2n}C_n\)</p>
<p>(c) \({}^{2n}C_n = \dfrac{2^n[1\cdot3\cdot5\cdots(2n-1)]}{n!}\)</p>
<p>(d) None of the above</p>
Step-by-Step Solution
Key Concept: The identity (ⁿC₀)² + (ⁿC₁)² + ... + (ⁿCₙ)² = ²ⁿCₙ is the Vandermonde's convolution applied to choosing n items from 2n by pairing complementary binomial coefficients. This can be verified by recognizing that ²ⁿCₙ counts ways to select n objects from two groups of n objects each.
<p><strong>Step 1: Understand the Combinatorial Argument</strong></p><p>We have 2n places total. We need to choose exactly n places for boys (remaining n for girls).</p><p>This can be done in ²ⁿCₙ ways. ✓</p><p><strong>Step 2: Prove the Identity Using Counting Principle</strong></p><p>Alternative approach: Suppose we have n boys and n girls. We want to select exactly n people.</p><p>We can select k boys (in ⁿCₖ ways) and (n-k) girls (in ⁿCₙ₋ₖ = ⁿCₖ ways).</p><p>Total ways = Σ(k=0 to n) ⁿCₖ · ⁿCₖ = Σ(k=0 to n) (ⁿCₖ)²</p><p><strong>Step 3: Equate Both Methods</strong></p><p>Direct selection of n people from 2n = ²ⁿCₙ</p><p>Selection via boys-girls partition = Σ(k=0 to n) (ⁿCₖ)²</p><p>Therefore: (ⁿC₀)² + (ⁿC₁)² + ... + (ⁿCₙ)² = ²ⁿCₙ</p><p>∴ The statement and the identity are <strong>both correct</strong>. The options A, B, C are all valid interpretations or equivalent forms of this principle.</p>
Correct Answer: A, B, C