Let A = {1, 2,…, 10}. How many three-element subsets of A contain at least two consecutive integers?
I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets containing at least two consecutive integers, I thought to subtract from the total all subsets that do not contain consecutive integers.
I had some trouble understanding the general formula for determining the number of size-k subsets of a size-n set that don't contain consecutive integers, but this explanation helped.
Anyway, that gives me $\displaystyle \tbinom{10}{3}- \tbinom{n-k+1}{k}= 120 – \tbinom{10-3+1}{3}= 64$.
Did I miss anything?
Thanks!
Best Answer
First we add subsets by taking any of the $9$ pairs of consecutive integers $\{1,2\},\{2,3\},...,\{9,10\}$ and an arbitrary choice of the third element - in each case there are $8$ such choices, so this gives $9 \cdot 8 = 72$.
However, we see that any set of three consecutive integers $\{1,2,3\},\{2,3,4\},...,\{8,9,10\}$ has been counted twice, so we remove these. There are $8$ of them, so we subtract that and get $9\cdot 8 - 8 = 64$.