Choosing $5$ elements from first $14$ natural numbers so that at least two of the five numbers are consecutive

Question

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.

Answer 1

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 and no in total, but the last one will always be no, 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.

Answer 2

Finding the number of five element sets with the property that there are no consecutive numbers in it comes to finding the number of sums $$n_1+n_2+n_3+n_4+n_5+n_6=9$$ where $n_1$ and $n_6$ are nonnegative integers and $n_2,n_3,n_4,n_5$ are positive integers.

If we are working in set $\{1,\dots,14\}$ then e.g. solution $(0,2,3,1,2,1)$ represents the subset $\{1,4,8,10,13\}$.

This comes to the same as finding the number of sums $$m_1+m_2+m_3+m_4+m_5+m_6=5$$ where $m_1,m_2,m_3,m_4,m_5,m_6$ are nonnegative integers.

Here solution $(0,1,2,0,1,1)$ represents the subset $\{1,4,8,10,13\}$.

With stars and bars we find that there are: $$\binom{10}{5}$$ possibilities.

In total there are $\binom{14}5$ five element subsets of $\{1,\dots,14\}$ so:$$\binom{14}5-\binom{10}5$$of them will have a least one pair of consecutive numbers.