Solution: 2017 Fall Midterm - 1

Author: Michiel Smid

Question

Let $n \geq 8$ be an even integer and let $S = \{1,2,3,\dots,n\}$. Consider 7-element subsets of $S$ that consist of 4 even numbers and 3 odd numbers. How many such subsets are there?

(a)

${n \choose 4} + {n \choose 3}$

(b)

${n \choose 4} \cdot {n \choose 3}$

(c)

${n/2 \choose 4} + {n/2 \choose 3}$

(d)

${n/2 \choose 4} \cdot {n/2 \choose 3}$

Solution

1 is odd, 2 is even, 3 is odd, 4 is even, etc etc

This pattern of odd followed by even shows us that half the elements are even and half are odd.

We need to choose 4 even numbers from $ \frac{n}{2} $ even numbers.

There are $ \binom{ \frac{n}{2}}{4} $ ways to do this.

We need to choose 3 odd numbers from $ \frac{n}{2} $ odd numbers.

There are $ \binom{ \frac{n}{2}}{3} $ ways to do this.

Thus, there are $ \binom{ \frac{n}{2}}{4} \cdot \binom{ \frac{n}{2}}{3} $ ways to choose 4 even numbers and 3 odd numbers.