# 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.

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?

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}.$$

• Nice solution, but I really don't understand it. I tried creating a recurrence relation but have failed a lot, since it is a very difficult task. Here is the issue, we start with: $0$ then two options $1$ or another $0$, but if you choose $1$ then what? How does the recurrence form after that? Jul 19, 2015 at 18:13

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$

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 smaller number than $1280$, also because $\{1,2,\ldots,9,10\}$ has only $2^{10}=1024$ subsets. Jul 10, 2015 at 21:50
• @JackD'Aurizio : That too! ${}\qquad{}$ Jul 10, 2015 at 21:53

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.