Number Theory / Discrete Math

Question

Let T = (1,2,3.....,17)

1. How many subsets of T contain all of the odd integers in T?
2. How many subsets of T contain exactly 4 odd integers?
3. How man 9-element subsets of T contain exactly 4 odd integers?

Answer 1

1. First, we include all the odd integers in T. This leaves behind 8 integers to continue adding to our subsets. Since we can either choose to include each of these integers or not, there are 2^8 = 256 subsets of T containing all of its odd integers.
2. We do the same analysis above, but we multiply by the number of ways to choose the 4 odd integers. There are (9 choose 4) = 126 such ways, so there are 126*256 = 32256 total subsets containing exactly 4 odd integers.
3. We first choose the 4 odd integers (9 choose 4) = 126 ways. Then we choose the 5 even integers in our subset in (8 choose 5) = (8 choose 3) = 56 ways. Therefore there are 126*56 = 7056 such subsets.