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$
  • $\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 '18 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 '18 at 12:43
  • 1
    $\begingroup$ Maybe the Inclusion–exclusion principle could help here $\endgroup$ – Jon Aug 12 '18 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$ – Sufaid Saleel Aug 12 '18 at 13:07
  • 1
    $\begingroup$ @SufaidSaleel Are you sure of 2900? (my answer gives 2002-252=1750 as answer). $\endgroup$ – drhab Aug 12 '18 at 13:25
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$
  • $\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$ – Sufaid Saleel Aug 13 '18 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 '18 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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