How many subsets of six integers chosen (without repetition) from 1,2,3,...20 are there with no consecutive integers(eg.,if 5 is in the subset, then 4 and 6 cannot be in it)?
Answers
Answer:
It's probably easier to count how many actually have two consecutive integers and subtract that from the total number of three element subsets.
First we note that there are 18 subsets with all elements consecutive.
Now we wish count the number of three element subsets such that exactly two elements are consecutive. First, let's count the number of these subsets which additionally have the non-consecutive element as the largest. If the consecutive elements are n−1 and n, then the remaining element can be any of the numbers n+2,n+3,…,20. Since the lowest n can be is 2, we get
17+16+⋯+1=17×182=153
subsets of this form. By symmetry we also have 153 subsets which have the non-consecutive element as the smallest.
This gives us a total of 18+153+153=324 subsets with two consecutive elements.
The total number of subsets is (203)=20×19×186=1140, so by subtraction we find the total number with no consecutive elements is 1140−324=816.