How do I find total number of possible arrangements in the following case?

Question

There are n seats in a row and we have to arrange people on these seats such that there must be at least two people in the row and no two people sits adjacent. For instance, if n=5 then there are following arrangements possible(dots represent seats and x represents person sitting on that seat).

x.x.x

..x.x

.x..x

.x.x.

x...x

x..x.

x.x..

So total 7 arrangements are possible hence answer is 7.

I tried some gap methods but I am not able to solve it.

Answer 1

Suppose that there are $k$ people and we have to seat them in $n$ places so that no two are adjacent. Consider the $n-k$ unoccupied seats. There are $n-k+1$ gaps between them and choosing $k$ out of these gaps, we can place the $k$ people and $n-k$ empty seats so that no two are adjacent. Thus this number is $\binom{n-k+1}{k}$. The maximum number of people so that no two are adjacently seated is $[\frac{n+1}{2}]$. Thus the required number is \begin{equation*} \sum_{k=2}^{[\frac{n+1}{2}]} \binom{n-k+1}{k} \end{equation*} For $n=5$, this number is \begin{equation*} \binom{4}{2} + \binom{3}{3} = 7 \end{equation*} In the above we have assumed that people are "indistinguishable". If you want to consider arrangements in which the arrangement of people must be taken into account (with no two looking alike), the number is \begin{equation*} \sum_{k=2}^{[\frac{n+1}{2}]} k!\binom{n-k+1}{k} \end{equation*}

Answer 2

Ok, using your gap method, let me work out more simply for $n=5$

If you have $2$ seated people, there must be $3$ vacant chairs, $\uparrow \boxed.\uparrow\boxed.\uparrow\boxed.\uparrow$
and you can seat the two people at the uparrows in $\binom42$ = 6 ways

If you have $3$ seated people, there must be $2$ vacant chairs, $\uparrow \boxed.\uparrow\boxed.\uparrow$,
and you can seat the three people at the uparrows in $\binom33$ ways

If $n$ is even, the pattern will be marginally different, e.g. for $n=8$,
you can work out that at most $4$ people can be seated, in $\binom72 + \binom63 + \binom54$ ways.

You should be able now to derive a general formula with
number of seats $=n$, and (say) number of seated people $=k$

Further hovering hint

If there are $k$ seated people, there are $(n-k)$ vacant seats, and $2\le k\le(n-k+1)$

so

$k \le (n-k+1) \to n \le \frac{n+1}{2} \le \lfloor{\frac{n+1}{2}}\rfloor$

and ans is

$\sum_{k=2}^{\lfloor{\frac{n+1}{2}}\rfloor} \binom{n-k+1}{k}$

---

Added

Like you, I have taken people to be unlabelled, say people sitting in a cinema hall.