Inclusion-Exclusion principle problem 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.
 A: 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 $.
A: 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.)
