Permutations & Combinations
Combinations with Odd/Even Partition
Grade 11
Question:
<p>Let <i>S</i> = {1, 2, 3, ..., 9}. For <i>k</i> = 1, 2, ..., 5, let <i>N<sub>k</sub></i> be the number of subsets of <i>S</i>, each containing five elements out of which exactly <i>k</i> are odd. Then <i>N</i><sub>1</sub> + <i>N</i><sub>2</sub> + <i>N</i><sub>3</sub> + <i>N</i><sub>4</sub> + <i>N</i><sub>5</sub> = ?</p>
<p>(A) 125</p>
<p>(B) 252</p>
<p>(C) 210</p>
<p>(D) 126</p>
Step-by-Step Solution
Key Concept: Use combinations to count subsets with exactly k odd numbers from a set containing 5 odd and 4 even numbers.
<p><strong>Step 1:</strong> Set <i>S</i> = {1, 2, 3, ..., 9} has 5 odd numbers {1, 3, 5, 7, 9} and 4 even numbers {2, 4, 6, 8}.</p><p><strong>Step 2:</strong> We need subsets with exactly 5 elements, where exactly <i>k</i> are odd.</p><p><strong>Step 3:</strong> For each subset:
<br/>• <i>N</i><sub>1</sub> = choose 1 odd and 4 even = \(\binom{5}{1}\binom{4}{4}\) = 5 × 1 = 5
<br/>• <i>N</i><sub>2</sub> = choose 2 odd and 3 even = \(\binom{5}{2}\binom{4}{3}\) = 10 × 4 = 40
<br/>• <i>N</i><sub>3</sub> = choose 3 odd and 2 even = \(\binom{5}{3}\binom{4}{2}\) = 10 × 6 = 60
<br/>• <i>N</i><sub>4</sub> = choose 4 odd and 1 even = \(\binom{5}{4}\binom{4}{1}\) = 5 × 4 = 20
<br/>• <i>N</i><sub>5</sub> = choose 5 odd and 0 even = \(\binom{5}{5}\binom{4}{0}\) = 1 × 1 = 1</p><p><strong>Step 4:</strong> Sum = 5 + 40 + 60 + 20 + 1 = 126</p><p>∴ Answer is D.</p>
Correct Answer: D