# Probability question regarding taking seats

Suppose there are $$N$$ seats and people come in one by one to take a seat randomly. They cannot take a seat that has been taken or is neighbor to a seat that has been taken. The process stops when there are no more valid seats available. What is the expected number of seats taken at the end?
My solution is kind of brute force - let $$f(n)$$ be the expected number of seats taken if there are $$n$$ seats to start with, then we have the recursion that when $$n\geq4$$ $$f(n)=\frac{2}{n}f(n-2)+\frac{1}{n}[(f(0)+f(n-3))+(f(1)+f(n-4))+...+(f(n-3)+f(0))]$$ since with $$\frac{1}{n}$$ probability the first person takes the first seat, which marks two seats unavailable, same situation if they take the last seat, otherwise they would mark three seats unavailable. Simplifying we get $$f(n)=f(n-2)+\frac{2}{n}f(n-3)+\frac{2}{n}$$ Still without a nice closed form expression. Is there a nicer way to solve this problem with a closed form expression?

• Did you try getting a differential/integral equation for the generating function of $f(n)$ and solving it/feeding it into a CAS? Aug 8, 2020 at 19:46
• Alternatively (just barely simpler) : $$f(n) = \frac{1+(n-1) f(n-1) +2 f(n-2)}{n}$$ Aug 8, 2020 at 21:22
• Are the seats arranged in a loop or is it a line? The answer for each changes.
– 24n8
May 10, 2021 at 21:28
• Seats are arranged in a line May 11, 2021 at 1:05

Please note the number of seats taken (say, $$m$$ out of $$n$$) can be between one third to half. You will have to apply the ceiling function to get the exact number.
$$\lceil{\dfrac{n}{3}}\rceil \le m \le \lceil{\dfrac{n}{2}}\rceil$$
For example, take $$n = 11$$, there are possibilities of $$4$$ seats taken, $$5$$ seats taken and $$6$$ seats taken. You get that using the above range.