Let $S = \{1, 2, 3, ..., 9\}$. For $k = 1, 2, ..., 5$, let $N_k$ be the number of subsets of $S$, each containing five elements out of which exactly $k$ are odd. Then $N_1 + N_2 + N_3 + N_4 + N_5 =$

Let S = {1, 2, 3, ..., 9}. For k = 1, 2, ..., 5, let Nₖ be the number of subsets of S, each containing five elements out of which exactly k are odd. Then N₁ + N₂ + N₃ + N₄ + N₅ = $S = \{1,2,3,\ldots,9\}$ $N_k = \#\{\,T \subseteq S : |T|=5,\ \text{exactly } k \text{ of its elements are odd}\,\}$ $\text{Find } N_1 + N_2 + N_3 + N_4 + N_5.$ $\text{(1) } 210 \qquad \text{(2) } 252 \qquad \text{(3) } 125 \qquad \text{(4) } 126$ $N_k = \binom{5}{k}\binom{4}{5-k}$ $\text{Odd} = \{1,3,5,7,9\}\ (5), \qquad \text{Even} = \{2,4,6,8\}\ (4)$ $N_1 = \binom{5}{1}\binom{4}{4} = 5 \times 1 = 5$ $N_2 = \binom{5}{2}\binom{4}{3} = 10 \times 4 = 40$ $N_3 = \binom{5}{3}\binom{4}{2} = 10 \times 6 = 60$ $N_4 = \binom{5}{4}\binom{4}{1} = 5 \times 4 = 20$ $N_5 = \binom{5}{5}\binom{4}{0} = 1 \times 1 = 1$ $5+40+60+20+1 = 126$ $\sum_{k=1}^{5} N_k = \binom{9}{5} = 126 \quad \checkmark$ $\boxed{\text{(4) } 126}$