New Year's Countdown Day 8: Eight Seated People

我们将A除外，原问题化为F（7）的子问题，将A插回，A不能在B的右边与H的左边，A只有5个位置，5F（7）。
考虑BH相连的情况，将BH当作一个位置，此时A有6个位置，6F（6）。
考虑A在BC，CD，DE，EF，FG，GH之间，6F（6）。
考虑BH相连，并且A在BC，CD，DE，EF，FG，GH之间，6F（5）
F（8）=5F（7）+6F（6）+6F（6）+6F（5）
F（n）=(n-3)F（n-1）+2(n-2)F（n-2）+(n-2)F（n-3）
F(2)=0,F(3)=1,F(4)=1,F(5)=8,F(6)=36，F（7）=229，F（8）=1625

Say there are n persons. Let F(n) be the number of allowed arrangements with n persons. So we are looking for F(8).

(1) There are $(n-1)!$ seatings that are rotationally different. (Although most of them are not allowed).

(2) We can reduce all these seatings into groups of sequences: the candidate rearrangement $abdefgch$ becomes $\{defg\}\{c\}\{hab\}$ , a group of 3 sequences. With sequence, I will mean a (maximum) list of persons who are sitting next to each other in the original seating. Note that we may have to put the tail and the head into one sequence, as in the example above. There are ${n \choose k}$ distinct groups of $k$ such sequences (choose $k$ persons to start a new sequence). Each such a group of $k$ sequences can be arranged in F(k) ways (other arrangements of the $k$ sequences wouldn't "break" the seating in $k$ sequences, but instead consist of $k-1$ or even less sequences). The only exception is the sequence of all $n$ persons. The ${n \choose 1}$ possibilities for a single sequence ${a_1a_2...a_n}$ are all rotational the same.

Combined, we get $\displaystyle 1 + \sum_{k=3}^n {n \choose k}*F(k)=(n-1)!$

We can now finaly resolve the $F(n)$ recursively: $F(1)=1, F(2)=0, F(3)=1, F(4)=1, F(5)=8, F(6)=36, F(7)=229, F(8)=1625$ .

So the final answer to this question is: $\boxed{1625}$ .

A guess, using Stirling numbers of the first kind: The reflected arrangement given as an example in the problem is one solution, and then every transformation to all other solutions — choosing, say, 'A' as the fixed point — count up to |s(7,3)|. So then 1 + 1624 would add up to 1625. But I can't quite figure out how partitioning the other seven letters into three cycles works out.

This could be an easy solution:

from itertools import permutations

def check_rotation(l):
    for i in range(len(l)-1):
        if l[i+1]-l[i] == 1:
            return True
    return False 

n = 8
counter = 0;

for l in permutations(range(n)):
    if l[0] == 1:
        break
    if l[n - 1] == n-1:
        continue
    if not check_rotation(l):
        counter += 1

print(counter)