1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I think you have double counts here, think for example how many times you count the set $\left\{ 1,2,3,4,5\right\} $ $\endgroup$
    – Jon
    Aug 12, 2018 at 12:43
  • $\begingroup$ @SufaidSaleel Do the $5$ numbers have to be all unique? I assumed they didn't have to be in my answer. $\endgroup$
    – Toby Mak
    Aug 12, 2018 at 12:43
  • 1
    $\begingroup$ Maybe the Inclusion–exclusion principle could help here $\endgroup$
    – Jon
    Aug 12, 2018 at 12:55
  • $\begingroup$ I am done. Thanks a lot for your help! The answer is 2900.I have done it by inclusion-exclusion principle! $\endgroup$ Aug 12, 2018 at 13:07
  • 1
    $\begingroup$ @SufaidSaleel Are you sure of 2900? (my answer gives 2002-252=1750 as answer). $\endgroup$
    – drhab
    Aug 12, 2018 at 13:25

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @drahab how you have written $n_1+n_2+n_3+n_4+n_5+n_6=9$. What are these?I cannot realise what do by these. $\endgroup$ Aug 13, 2018 at 2:28
  • $\begingroup$ If e.g. the selected subset is $\{1,4,8,10,13\}$ then $n_1$ stands for the number of elements in the original set $<1$ so equals 0. $n_2$ for the number of elements in between $1$ and $4$ so equals $2$. $n_3$ for the number of elements in between $4$ and $8$ so equals $3$. Et cetera. Finally $n_6$ stands for the number of elements larger than $13$ so equals $1$. To avoid that numbers are consecutive the $n_i$ must be positive with exception for the first and the last. $\endgroup$
    – drhab
    Aug 13, 2018 at 6:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .