11
$\begingroup$

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$,

In a way where we have no consecutive numbers in the set? (like $1,2$)

$\endgroup$
  • 1
    $\begingroup$ Does the order of choosing matter? $\endgroup$ – Daniel Fischer Sep 11 '13 at 9:43
  • 1
    $\begingroup$ No. I said we choose it to a set... $\endgroup$ – NightRa Sep 11 '13 at 9:50
  • $\begingroup$ is there any way to find no of ways of choosing r numbers from 1 to N such that difference between no such pair exists where difference is equal to (k=13)? . For e.g. in the above question k = 1 $\endgroup$ – Nimish Bansal Oct 18 '18 at 12:05
14
$\begingroup$

Assuming that the order of choice doesn’t matter, imagine marking the positions of the $r$ chosen numbers and leaving blank spaces before, between, and after them for the $n-r$ non-chosen numbers; if $r=3$, for instance, you’d get a skeleton like $_|_|_|_$, where the vertical bars represent the positions in $1,2,\ldots,n$ of the chosen numbers. The remaining $n-r$ numbers must go into the $r+1$ open slots in the diagram, and there must be at least one of them in each of the $r-1$ slots in the middle. After placing one number in each of those slots, we have $n-r-(r-1)=n-2r+1$ numbers left to place arbitrarily in the $r+1$ slots. This is a standard stars-and-bars problem: there are

$$\binom{(n-2r+1)+(r+1)-1}{(r+1)-1}=\binom{n-r+1}r$$

ways to do it. The reasoning behind the formula is reasonably clearly explained at the link.

$\endgroup$
  • 1
    $\begingroup$ Here is an answer than (in my opinion) provides a slightly clearer/more intuitive explanation: math.stackexchange.com/questions/677354/… $\endgroup$ – 1110101001 Oct 11 '14 at 19:26
  • $\begingroup$ @user2612743: You mean the accepted answer there? It’s basically just the explanation at the link in mine. $\endgroup$ – Brian M. Scott Oct 11 '14 at 19:27
  • $\begingroup$ @BrianM.Scott How to approach this problem when numbers are arranged in a circle? $\endgroup$ – Mathematics Feb 20 '16 at 13:03
  • 2
    $\begingroup$ @Mathematics: If the numbers are arranged in a circle, there are $r$ spaces instead of $r+1$, because the end spaces are actually the same space. $\endgroup$ – Brian M. Scott Feb 20 '16 at 17:56
0
$\begingroup$

first we decide, that we will start choosing in an increasing manner... once we have chosen an $i$ we Will not chose any number from $i-1$ to $1$. so after choosing a number we must not choose the next number and thus choosing $r$ numbers we must leave $r-1$ numbers as choosing the last number we will have no restriction for the next.where $r$ is the number of objects to be chosen. so we leaving $r-1$ numbers, we have $n-(r-1)$ or $n-r+1$ numbers remaining. and we can choose $r$ numbers in $\binom{n-r+1}r$ ways.

$\endgroup$
  • $\begingroup$ What exactly is $k$? $\endgroup$ – martini Apr 9 '15 at 9:26
  • $\begingroup$ k was the number of objects to be chosen.. i edited the above answer replacing k by r, which was given in the question $\endgroup$ – Sampadl Apr 11 '15 at 3:52

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.