# Choosing numbers without consecutive numbers.

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$)

• Does the order of choosing matter? – Daniel Fischer Sep 11 '13 at 9:43
• No. I said we choose it to a set... – NightRa Sep 11 '13 at 9:50
• 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 – Nimish Bansal Oct 18 '18 at 12:05

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.

• Here is an answer than (in my opinion) provides a slightly clearer/more intuitive explanation: math.stackexchange.com/questions/677354/… – 1110101001 Oct 11 '14 at 19:26
• @user2612743: You mean the accepted answer there? It’s basically just the explanation at the link in mine. – Brian M. Scott Oct 11 '14 at 19:27
• @BrianM.Scott How to approach this problem when numbers are arranged in a circle? – Mathematics Feb 20 '16 at 13:03
• @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. – Brian M. Scott Feb 20 '16 at 17:56

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.

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