A007973 Number of permutations that are n-2 "block reversals" away from 12...n.

1, 3, 15, 55, 184, 648, 2111, 6352, 17337, 42878

Offset

2,2

Links

Table of n, a(n) for n=2..11.

Formula

a(n) = A300003(n,n-2).

Prog

(Python)
def a(n):
    perm = tuple(range(1, n+1)); reach = {perm}; frontier = {perm}
    for k in range(n-2):
        r1 = set()
        while len(frontier) > 0:
            q = frontier.pop()
            for i in range(n):
                for j in range(i+1, n+1):
                    qp = list(q)
                    qp[i:j] = qp[i:j][::-1]
                    qp = tuple(qp)
                    if qp not in reach:
                        reach.add(qp)
                        r1.add(qp)
        frontier = r1
    return len(frontier)
print([a(n) for n in range(2, 10)]) # Michael S. Branicky, Jan 26 2023

Crossrefs

Cf. A007972, A007974, A007975, A300003.

Sequence in context: A119113 A286185 A152896 * A261737 A015249 A084152

Adjacent sequences: A007970 A007971 A007972 * A007974 A007975 A007976

Keyword

nonn,more

Author

J. H. Conway

Extensions

a(9)-a(11) from Sean A. Irvine, Feb 22 2018

Status

approved