# 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? Sep 11 '13 at 9:43
• No. I said we choose it to a set... 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 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/… Oct 11 '14 at 19:26
• @user2612743: You mean the accepted answer there? It’s basically just the explanation at the link in mine. Oct 11 '14 at 19:27
• @BrianM.Scott How to approach this problem when numbers are arranged in a circle? 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. 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.

Let $$g(n,r)$$ be the answer to the OP's question.

There is a simple recursion that $$g$$ satisfies.

$$\tag 1 g(n+1,r) = g(n,r) + g(n-1,r-1)$$

To see this consider the set $$\{1,2,3,\dots,n,n+1\}$$. We can partition the solution set (subsets with $$r$$ elements) into those that contain the number $$n+1$$, call it $$\mathcal N$$, and those that don't, call it $$O$$.

If $$A \in \mathcal N$$ then $$n \notin A$$ and clearly $$|\mathcal N| = g(n-1,r-1)$$.

If $$A \in \mathcal O$$ then $$n+1 \notin A$$ and clearly $$|\mathcal O| = g(n,r)$$.

The total sum is the sum of the blocks, giving us $$\text{(1)}$$.

The function $$g$$ satisfies boundary conditions and without finding a closed formula for $$g$$ we can still use a computer program to calculate $$g(n,r)$$ - see the next section.

There are many paths you can take if you work on finding a closed formula for $$g$$. No doubt, you will eventually find that

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

When you plug this into $$\text{(1)}$$ you will see Pascal's rule on your scrap paper.

Python program (using a recursive function)

def daH(x:int,y:int):        # g(x,y)=g(x-1,y)+g(x−2,y−1)
if y == 1:               # on wedge boundary output known
return x
if x == 2 * y - 1:       # on wedge boundary output known
return 1
r = daH(x-1,y) + daH(x-2,y-1)
return r

print('g(7,4)  =', daH(7,4))
print('g(10,4) =', daH(10,4))


OUTPUT:

g(7,4)  = 1
g(10,4) = 35