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

Author

Sean A. Irvine, Feb 22 2018

Keywords

• nonn
• tabf

Examples

			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.
		

Links

• Bert Dobbelaere, Table of n, a(n) for n = 0..105, terms n=0..78 from Sean A. Irvine.

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.

Cf. A380576.

Programs

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

Formula

Sum_{k>=1} k * T(n,k) = A380576(n). - Alois P. Heinz, Mar 26 2025