Inclusion-Exclusion principle problem

Question

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.

Answer 1

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

Answer 2

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