Arrangements of Chairs in a Circle 
Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Hints only please!
This is a confusing worded-problem. 
We could break it into, $7$ cases but that would take very long? 
Case 1: 3 chairs adjacent. 
Ways to do this: $$\binom{10}{3} \cdot \binom{7}{7} = 120$$
But I see that, for the next, $\binom{10}{4}$. 
So it will be:
$$1 + \binom{10}{3} + \binom{10}{4} + \binom{10}{5} + \binom{10}{6} + \cdots + \binom{10}{9}$$
$$= 1 + 120 + 210 + 252+\cdots$$
But this isnt a legit method it looks like.
I am not sure how to use PIE/anything else here?
 A: We may count how many "circular strings" over the alphabet $\Sigma=\{0,1\}$ do not have three consecutive $1$s. Let $A_n$ be the number of regular strings in $\Sigma^n$ without three consecutive ones, and $C_n=|A_n|$. Since $a\in A_n$ may start only with $0,10,110$, we have:
$$ C_1=2,C_2=4,C_3=7,\qquad C_n=C_{n-1}+C_{n-2}+C_{n-3} $$
so $C_n$ is a tribonacci number. Let we fix a conventional starting point in our circular strings avoiding $111$, by denoting it with a dot. We have the following possibilities:
$$ 0.0\quad 01.0\quad 011.0\quad 0.10\quad 01.10\quad 0.110\quad $$
so the number of circular strings with length $10$ avoiding $111$ is given by:
$$ C_8+C_7+C_6+C_7+C_6+C_6 = C_8+2C_7+3C_6 = 149+2\cdot 81+3\cdot 44 = \color{blue}{443} $$
and the wanted number of subsets is given by:
$$ 2^{10} - \color{blue}{443} = \color{red}{581}.$$
A: Another approach is to count the good configurations directly.  There is one subset of size $10$, ${10 \choose 9}=10$ of size $9$, ${10 \choose 8}=45$ of size $8$ and ${10 \choose 7}=120$ of size $7$.   All $176$ of these have three chairs in a row.   
There are $10$ subsets of size $3$ that have three in a row.  For subsets of size $4$ there are $10$ ways to choose the first of the three and six places for the other one where we exclude the one just before the three to avoid double counting four in a row.  That gives $60$.  For subsets of size $5$ there are $10$ ways to choose the three in a row and ${6 \choose 2}=15$ ways to choose the two others, again disallowing the one just before the set of three.  That gives $150$.  This paragraph totals $220$.  
Finally we have subsets of size $6$.  We follow the same approach as with $5$, choosing a block of three in $10$ ways, then choosing the three others in ${6 \choose 3}=20$ ways.  There are fifteen configurations with two isolated sets of three, which we have counted twice.  That gives $185$ subsets.  
The grand total is $176+220+185=581$
A: The number of sets of exactly three adjacent chairs is $10$.  Either they're chairs $1$, $2$, and $3$, or $2,3,4$, or $3,4,5$, etc.  After $8,9,10$ comes $9,10,1$ and then $10,1,2$.
The number of subsets of the remaining set of seven chairs is $2^7=128$.
However, if one just picks $10\times128=1280$, then one is counting some combinations more than once.  For example, if one has $1,2,3,4,6,7,8$, then one counts each of these:
\begin{align}
& \underbrace{1,2,3,}\ 4, 6, 7, 8 \\[10pt]
& 1,\ \underbrace{2,3,4,}\ 6,7,8 \\[10pt]
& 1,2,3,4,\ \underbrace{6,7,8}
\end{align}
But they're really all three the same combination and should be counted only once.  One should therefore expect a smaller number than $1280$.
So I would search for combinations in which no chairs are adjacent or in which exactly two chairs are adjacent, and subtract that from the total number of subsets.
A: This probably isn't the elegant answer they were looking for, but if you consider the chairs to be ordered linearly (not circularly) then the number of ways of NOT getting 3 chairs in a row, as a function $F(n,k)$ of the number of such subsets of $n$ chairs that can be chosen linearly such that there is no contiguous subset of $3$ chairs chosen, and ends with $k$ contiguous chairs chosen, then you get:
$$F(n,0) = F(n-1,0) + F(n-1,1) + F(n-1,2)$$
$$F(n,1) = F(n-1,0)$$
$$F(n,2) = F(n-1,1)$$
Of course, then you need to take care of the circularity of the chairs and so you'll need to break into cases as to whether the initial binary indicator sequence of 2 chairs that may be taken is $00$, $01$, $10$, or $11$. Since $11$ and $10$ are the only possibilities for initial sequence that can cause you trouble when you choose the last 2 chairs, where you may get 3 contiguous chairs that cross the starting point of the circle, you can probably just keep track of each of those subcases separate and lump $00$ and $01$ starting sequences together.
