Permutations & Combinations
Selection using generating functions
Grade 11
Question:
<p>Let N denote the number of ways in which 3n persons can be selected from 2n men, 2n women and 2n kids. Then</p>
<p>(a) N = coefficient of \(t^{3n}\) in \((1-t^{2n+1})^3(1-t)^{-3}\)</p>
<p>(b) \(N = {}^{3n+2}C_{3n} - 3 \cdot {}^{n+1}C_n - 1\)</p>
<p>(c) N = coefficient of \(t^{3n}\) in \((1-3t^{2n+1})(1+{}^3C_1\,t + {}^4C_2\,t^2 + {}^5C_3\,t^3 + \ldots)\)</p>
<p>(d) \(N - 1 > 3n^2\)</p>
Step-by-Step Solution
Key Concept: Recognize that selections from three disjoint groups follow the multiplication principle: total ways = Σ(selecting i men) × (selecting j women) × (selecting k kids) where i+j+k=3n. This sum equals the coefficient of x^(3n) in the expansion of (1+x)^(2n) × (1+x)^(2n) × (1+x)^(2n) = (1+x)^(6n).
<p><strong>Step 1:</strong> Set up the generating function for selecting from three independent groups. For 2n men, 2n women, and 2n kids, the generating function is (1+x)^(2n) × (1+x)^(2n) × (1+x)^(2n) = (1+x)^(6n).</p><p><strong>Step 2:</strong> The coefficient of x^(3n) in (1+x)^(6n) gives the total number of ways to select 3n persons from 6n people (where the composition of men, women, kids varies).</p><p><strong>Step 3:</strong> The coefficient of x^(3n) in (1+x)^(6n) is C(6n, 3n).</p><p><strong>Verification:</strong> By the trinomial identity, N = Σ C(2n,i) × C(2n,j) × C(2n,k) where i+j+k=3n, and this sum equals C(6n,3n) by the convolution property of binomial coefficients.</p><p>∴ Answer: N = C(6n, 3n)</p>
Correct Answer: A