15
$\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 '13 at 9:43
  • 1
    $\begingroup$ No. I said we choose it to a set... $\endgroup$
    – NightRa
    Sep 11 '13 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 '18 at 12:05
20
$\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
  • 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$ Oct 11 '14 at 19:27
  • $\begingroup$ @BrianM.Scott How to approach this problem when numbers are arranged in a circle? $\endgroup$ 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$ 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$
0
0
$\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$

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.