Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
Hmm, this really doesn't deserve upvotes, I started writing a solution but it ended up becoming essentially the same as 'tfw cant into math's answer, so I took another approach which I seriously cannot recommend. –  copper.hat Oct 24 '13 at 22:28

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.