Let $n$ be the number of five element subsets that can be chosen from the set of the first $14$ natural numbers so that at least two of the five numbers are consecutive. Find $n$.
My work I have made a block of two consecutive numbers (like $(1,2), (2,3), (13,14)$ etc.). Now we can choose this block in $13$ ways. Now we have to choose $3$ numbers from the rest $12$ numbers. We can do it in $12 \choose 3$ ways. So, by multiplication principle we come to know that there are $13 \times {12\choose 3}$ ways .
Am I right? Please tell where I had made the mistake?
All the $5$ elements are distinct. I didn't ask to arrange the group. I ask the number of sets only.
Best Answer
Your method will overcount selections such as $\{4,5,6,9,10\}$ because it will arise from $4,5$ or $5,6$ or $9,10$ as the initial pair.
It is simpler first to count all subsets of size $5$, and then subtract the number of such subsets that have no neighboring elements.
The latter count can be found by considering you have to choose some order to put $5$
yes then no
and $5$no
together. This will give a sequence of $15$yes
andno
in total, but the last one will always beno
, so it gives you exactly the way of placing $5$yes
on $\{1,2,3,\ldots,14\}$ such that no two of them are neighbors.