Chair arrangements with small gaps Given $N$ chairs, how many ways are there to sit people such that there is no contiguous gap of $k$ or more empty chairs between them?
Formally, how many subsets $S \subseteq \{1,2,\ldots, N\}$ are there satisfying that for all $x < y \in S$ s.t. $\{x+1, x+2, \ldots, y-1 \} \subset S^c$, then $y-x \leq k$?
Asymptotics in $N$ are welcome too. Thanks!
 A: There's general machinery that answers questions like this (basically you construct a finite graph such that walks on this graph count the thing you're interested in) but in this particular case it can be avoided using a more direct counting argument. An equivalent question is to count the number of binary strings of length $N$ which do not contain $k$ consecutive zeroes between any two ones. Let $a_k(N)$ denote the number of such strings.
We can count these strings by factoring them based on how their zeroes are sandwiched by their ones. Aside from the zero string, any such string begins with an initial run of arbitrarily many zeroes, then a product of factors of the form $1, 10, 100, \dots $ up to $1(0)^{k-1}$ (meaning $1$ followed by $k-1$ zeroes), then a final $1$ followed by a final run of arbitrarily many zeroes. This gives that the generating function of $a_k(N)$ is
$$\sum_{N \ge 0} a_k(N) t^N = \frac{1}{1 - t} \frac{1}{1 - t - t^2 \dots - t^k} \frac{t}{1 - t} + \frac{1}{1 - t}.$$
The case $k = 1$ is somewhat degenerate and gives a generating function $\frac{t}{(1 - t)^3} + \frac{1}{1 - t}$ which recovers your count in the comments. When $k = 2$ that middle factor $\frac{1}{1 - t - t^2}$ is the generating function of the Fibonacci numbers.
In general, this generating function tells us that $a_k(N)$ is asymptotically $c_k r_k^N$ where $r$ is the largest root of the polynomial $p_k(t) = t^k - t^{k-1} - t^{k-2} - \dots - 1$ obtained by reversing the polynomial in the denominator above and $c_k$ is a constant that can be computed by computing the residue of the generating function at $t = \frac{1}{r_k}$. It's not hard to guess that $\lim_{k \to \infty} r_k = 2$. To put some explicit numbers to this,
$$r_2 = \frac{1 + \sqrt{5}}{2} = 1.618 \dots$$
$$r_3 = 1.839 \dots $$
$$r_4 = 1.928 \dots $$
so the convergence is even pretty rapid. We can say more about it by massaging the defining polynomial a bit, into the form $p_k(t) = t^k - \frac{t^k - 1}{t - 1}$, so that setting this equal to zero and rearranging a bit gives $t = 2 - \frac{1}{t^k}$. Since $r_k \approx 2$, substituting this in gives $r_k \approx 2 - \frac{1}{2^k}$, which gives $\boxed{ a_k(N) \approx c_k \left( 2 - \frac{1}{2^k} \right)^N }$. (In fact we have $r_k < 2$ which gives $r_k < 2 - \frac{1}{2^k}$.)
This asymptotic can be motivated heuristically as follows. Suppose we consider a random binary string of length $N$; what can we say about the probability that it does not contain $k$ consecutive zeroes? (It's a little simpler to argue about this sequence than yours but the asymptotics are the same up to a constant factor.) If we consider each block of $k$ consecutive digits it has probability $\frac{1}{2^k}$ of being all zeroes. Moreover, for blocks that are not too close together, the events that each block consists of $k$ consecutive zeroes are approximately independent; if they were exactly independent (which of course they are not) then we'd get that the probability of not containing any $k$ consecutive zeroes is about $\left( 1 - \frac{1}{2^k} \right)^N$. The asymptotic above corresponds to a probability of about $\left( 1 - \frac{1}{2^{k+1}} \right)^N$ so this is pretty close.

For the general theory of sequences with rational generating functions, which is quite pleasant and about which much can be said, you can consult, for example, Stanley's Enumerative Combinatorics Vol. I, Chapter 4. This theory implies, for example, that the sequence which counts strings containing no substring from a finite list of forbidden substrings also has a rational generating function, so also has an asymptotic of the form $N^k r^N$. (Here we essentially forbid the substring $0^k$ but not quite.) The same is true for any sequence counting the strings in a regular language, or equivalently a language recognized by a finite state machine, which contains the given problem as a special case.
