A300003 Triangle read by rows: T(n, k) = number of permutations that are k "block reversals" away from 12...n, for n >= 0, and (for n>0) 0 <= k <= n-1.

1, 1, 1, 1, 1, 3, 2, 1, 6, 15, 2, 1, 10, 52, 55, 2, 1, 15, 129, 389, 184, 2, 1, 21, 266, 1563, 2539, 648, 2, 1, 28, 487, 4642, 16445, 16604, 2111, 2, 1, 36, 820, 11407, 69863, 169034, 105365, 6352, 2, 1, 45, 1297, 24600, 228613, 1016341, 1686534, 654030, 17337, 2

Offset

0,6

Links

Sean A. Irvine, Table of n, a(n) for n = 0..78

Example

For n=3, the permutation 123 is reachable in 0 steps, 213 (reverse 12), 132 (reverse 23), 321 (reverse 123) are reachable in 1 step, and 231, 312 are reachable in 2 steps. Thus row 3 of the triangle is 1, 3, 2.
Triangle begins:
  1; (empty permutation, n = 0)
  1;
  1,   1;
  1,   3,   2;
  1,   6,  15,   2;
  1,  10,  52,  55,   2;
  1,  15, 129, 389, 184,   2;
The sum of row n is n! since each permutation of length n is accounted for in that row.

Prog

(Python)
def row(n):
    perm = tuple(range(1, n+1)); reach = {perm}; frontier = {perm}
    out = [1] if n == 0 else []
    for k in range(n):
        r1 = set()
        out.append(len(frontier))
        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 out
print([an for n in range(9) for an in row(n)]) # Michael S. Branicky, Jan 26 2023

Crossrefs

Cf. A000217 (column 1), A007972 (column 2), A007975 (column 3), A007973 (T(n, n-2)), A007974 (T(n, n-3)).

Row sums give A000142.

Sequence in context: A200536 A164645 A115755 * A259879 A016556 A067050

Adjacent sequences: A300000 A300001 A300002 * A300004 A300005 A300006

Keyword

nonn,tabf

Author

Sean A. Irvine, Feb 22 2018

Status

approved