Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We need to calculate the number of $r$-sized subsets of the set $\{1,\dots,n\}$ that don't contain any consecutive numbers.

We spent about 2 days on this...we know it's about the inclusion exclusion principle, and we have found something that works sometimes..but it doesn't cut it:

$$\binom n r$$ + This is a link to a sum we thought would work, any leads will be appreciated.

Some examples: For $n=4$, $r=3$, there are no valid groups.

For $n=4$, $r=2$ there are $3$ valid groups.

For $n=5$, $r=3$ there is $1$ valid group.

share|improve this question
    
$f(n+1,r+1)=f(n,r+1)+f(n-1,r)$. –  Gerry Myerson Aug 22 '13 at 12:54

2 Answers 2

Hint: Use stars and bars.

Pick $r$ numbers out of $n-r+1$.

Say the numbers are $a_1 < a_2< \ldots < a_r$. Then create a bijection with the set $b_i = a_i + i - 1$. This gives you all sequences of non-consecutive numbers, since $b_{i+1} - b_i = a_{i+1} + i - (a_i + i-1) \geq 2 $.

share|improve this answer

A) Represent the $n-r$ numbers that are NOT chosen by dots. They create $n-r+1$ gaps, and you need to choose $r$ of these gaps in which to put your selected numbers; so this can be done in $\binom{n-r+1}{r}$ ways. (Now count from left to right to see which numbers have been selected.)

Here is another way to do this:

B) Represent the $r$ numbers that are chosen by sticks, and set aside $r-1$ blockers (dots) to be inserted at the end to keep the numbers from being consecutive. This leaves $n-r-(r-1)$ numbers left to be arranged in the gaps created by the $r$ sticks, and the number of ways $n-r-(r-1)$ dots and $r$ sticks can be arranged in order is just $\binom{n-r+1}{r}$. (At the end, insert the blockers to keep the numbers from being consecutive.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.