How many 3-subsets of $\{1,2,\ldots,10\}$ contain at least two consecutive integers?

Question

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!

Answer 1

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$.

Answer 2

You could count the number of $3$ element subsets that have no consecutive integers.

The first number $n_1$ is taken from $1,...,6$ (any higher and there must be a consecutive pair). The next number $n_2$ is taken from $n_1+2,...,8$, and the last number $n_3$ is taken from $n_2+2,...,10$.

Summing gives \begin{eqnarray} \sum_{n_1=1}^6 \sum_{n_2=n_1+2}^8 \sum_{n_3=n_2+2}^{10} 1 &=& \sum_{n_1=1}^6 \sum_{n_2=n_1+2}^8 (9-n_2) \\ &=& \sum_{n_1=1}^6 \sum_{n_2=n_1}^6 (7-n_2) \\ &=& \sum_{n_1=1}^6 \sum_{n_2=1}^{7-n_1} (8-n_2-n_1) \\ &=& \sum_{n_1=1}^6 ((8-n_1)(7-n_1)-\frac{1}{2}(7-n_1)(8-n_1)) \\ &=& \sum_{n=1}^6 \frac{1}{2}(8-n)(7-n) \\ &=& \frac{1}{2} \sum_{n=1}^6 (n^2-15n+56) \\ &=& \frac{1}{2} (91-15\frac{1}{2}(6)(7)+6(56))\\ &=& 56 \end{eqnarray} Since $\binom{10}{3} = 120$, the answer is $120-56= 64$.

Answer 3

Alternatively, first count sets of the form $\{a,a+1,b\}$, where $b>a+1$. There are $8$ for $a=1$, there are $7$ for $a=2$, ... , and there's $1$ for $a=8$. That's 36 sets. Still to be counted are sets of the form $\{c,a,a+1\}$ with (to avoid re-counting any previously-counted sets) $c < a-1$. There is $1$ for $a=3$, there are $2$ for $a=4$, ..., and there are $7$ for $a=9$, for another $28$ sets. In all, there are $36+28$ = $64$ sets, which agrees with tfw's calculation.