Choosing spread out elements Is there an explicit formula that I'm missing, for the total number of choices from a set $S = \lbrace 1, 2 , \dots , n \rbrace$ such that for every choice $C \subset S$ the following holds: $\forall x, y \in C \phantom{10} \lvert y - x \rvert \gt r$ for some $r$?
A choice of exactly $k$ elements would amount to $\binom{n - r(k -1)}{k}$ though I can't seem to find much use out of that.
 A: Think of choosing $k$ things from $n$ as placing $k$ markers on a strip of $n$ squares.
Now, if you have to place your markers a distance $>r$ apart, you can enforce that by attaching to each marker a "tail" on (let's say) the right, of length $r$, and forbidding the (marker+tail) units to overlap. The tail can hang off the end of the strip; to fix that, increase the strip size by $r$.
And now take any configuration and shrink it down by just deleting the tails along with the squares they're on. The result is that we're now selecting $k$ things from not $n$ but $n-(k-1)r$. So the number of ways to choose $k$ $r$-separated things from $n$ is $\binom{n-(k-1)r}{k}$.
If you want the total number of ways to choose any number of things thus separated, it's $\sum_k\binom{n-(k-1)r}{k}$. That has an obvious closed form when $r=0$ and a somewhat-well-known expression in terms of Fibonacci numbers when $r=1$. What happens in general? Well, call that number $a_n$. You can take item 1, in which case you're forbidden to take items $2\dots r+1$ and your number of options is $a_{n-r-1}$. Or you can not take item 1, giving you $a_{n-1}$ possibilities. So $a_n=a_{n-1}+a_{n-r-1}$, and to determine all values from this recurrence relation we need to know $a_0$ up to $a_r$; within this range it's easy to see that $a_n=n+1$.
I don't know whether there's anything more closed-form for that total. I would guess not, on the grounds that I don't see any reason to expect the polynomial $t^{r+1}-t^r-1$ associated with the recurrence relation to be soluble by radicals in general, and if it isn't then I don't see any reason for there to be a closed form. But that's very handwavy.
Here's a relevant entry in the OEIS.
