login
Number of permutations that are n-3 "block reversals" away from 12...n.
4

%I #20 Jan 26 2023 16:14:12

%S 1,6,52,389,2539,16604,105365,654030,3900116

%N Number of permutations that are n-3 "block reversals" away from 12...n.

%F a(n) = A300003(n,n-3).

%o (Python)

%o def a(n):

%o perm = tuple(range(1, n+1)); reach = {perm}; frontier = {perm}

%o for k in range(n-3):

%o r1 = set()

%o while len(frontier) > 0:

%o q = frontier.pop()

%o for i in range(n):

%o for j in range(i+1, n+1):

%o qp = list(q)

%o qp[i:j] = qp[i:j][::-1]

%o qp = tuple(qp)

%o if qp not in reach:

%o reach.add(qp)

%o r1.add(qp)

%o frontier = r1

%o return len(frontier)

%o print([a(n) for n in range(3, 10)]) # _Michael S. Branicky_, Jan 26 2023

%Y Cf. A007972, A007973, A007975, A300003.

%K nonn,more

%O 3,2

%A _J. H. Conway_

%E a(9)-a(11) from _Sean A. Irvine_, Feb 22 2018