Find the number of subsets of $n$ chairs in a circle containing at least three adjacent chairs.
I know that the answer for $n=10$ is $581$, and the solution is here for instance.
I'm not sure if it's possible to derive a recurrence relation for this problem, but if it is, it would be very useful for the general case. In the case of 10 chairs, there are only two disjoint groups of four chairs, where in each group the first chair is not in the subset and the next three are in the subset, while for the general case, there could be arbitrarily many such groups. Such groups of four chairs exist iff not all chairs are filled, where a chair is filled if it's in a given subset. It seems that the principle of inclusion and exclusion would be too unwieldy for this problem; one could consider the number of subsets where adjacent chairs appear in groups of 1 or 2 and there is at least one group of 2 and the number of subsets where no chairs are adjacent. Note that the latter value is much easier to find than the former value and the latter value equals $\sum_k {n-k+1\choose k} – {n-k-3\choose k-2},$ where the sum is over nonnnegative integers k using the convention that ${n\choose k}=0$ for $n<k$.
Is there a recurrent relation for the general case?
Best Answer
Let's try counting arrangements of $n$ chairs in a circle with no three adjacent (call these arrangements "valid"). Since we're not looking at rotations as being equivalent, we can write an arrangement as a binary string by starting at a particular chair and working around the table; we'll use $1$ for a chair and $0$ for a gap. For example, the string $10101$ is valid; the string $10011$ is not.
The easiest way I found to think of these arrangements was to count valid strings grouped by patterns; eg counting how many valid arrangements start with $10$ and end with $1$. This allows us to break down the problem into more manageable recurrence relations by thinking about whether we can add a $1$ or a $0$ to the string and have it remain valid.
For example, to work out how many strings of length $n+1$ that fit the pattern $10\cdots1$, we look at how many valid strings of length $n$ start with $10$ and remain valid with another chair added at the end - ie precisely the number of valid strings of length $n$ with pattern $10\cdots0$.
The table below summarises the patterns and the relationships between them:
This looks horrendous, of course, but each of the patterns is easy to count. If we let $S(n)=a(n)+b(n)+c(n)+d(n)+e(n)+f(n)$ we can easily verify for small $n$ that $$S(n+1)=S(n)+S(n-1)+S(n-2)$$
and can prove this by complete induction; assume that $$S(k+1)=S(k)+S(k-1)+S(k-2)$$
for all $k<n$. Then $$\begin{align} S(n+1)&=a(n+1)+b(n+1)+c(n+1)+d(n+1)+e(n+1)+f(n+1) \\ &=[a(n)+b(n)+c(n)]+[a(n)]+[b(n)]+[d(n)+e(n)+e(n-1)]+[d(n)]+[f(n)+f(n-1)+f(n-2)] \\ &=S(n)+a(n)+b(n)+e(n-1)+d(n)+f(n-1)+f(n-2) \\ &=S(n)+[a(n-1)+b(n-1)+c(n-1)]+[a(n-1)]+[d(n-2)]+[d(n-1)+e(n-1)+e(n-2)]+f(n-1)+f(n-2) \\ &=S(n)+S(n-1)+a(n-1)+d(n-2)+e(n-2)+f(n-2) \\ &=S(n)+S(n-1)+[a(n-2)+b(n-2)+c(n-2)]+d(n-2)+e(n-2)+f(n-2) \\ &=S(n)+S(n-1)+S(n-2) \end{align}$$
so the relation holds for all $n$ - it's a tribonacci sequence.
It's a bit complicated to think about what these definitions mean for $n<3$, but it's easy to check the first few values of $S(n)$ are $S(3)=7$, $S(4)=11$, $S(5)=21$. Of course, the number of "invalid" arrangements (which have three adjacent tables) is just $2^n-S(n)$; for $n=3,4,\ldots$ these are $1,5,11,25,57,125,271,581,1233,2597$.
The sequence $S(n)$ is in OEIS, which has further discussion. The fact the recurrence ends up so nice makes me think there's a better approach!