18
$\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$
3
  • 1
    $\begingroup$ Does the order of choosing matter? $\endgroup$ Sep 11, 2013 at 9:43
  • 1
    $\begingroup$ No. I said we choose it to a set... $\endgroup$
    – NightRa
    Sep 11, 2013 at 9:50
  • 1
    $\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$ Oct 18, 2018 at 12:05

3 Answers 3

21
$\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$
4
  • 2
    $\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, 2014 at 19:26
  • $\begingroup$ @user2612743: You mean the accepted answer there? It’s basically just the explanation at the link in mine. $\endgroup$ Oct 11, 2014 at 19:27
  • $\begingroup$ @BrianM.Scott How to approach this problem when numbers are arranged in a circle? $\endgroup$ Feb 20, 2016 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$ Feb 20, 2016 at 17:56
1
$\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$
0
1
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

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