login
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.
6

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

%S 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,

%T 2539,648,2,1,28,487,4642,16445,16604,2111,2,1,36,820,11407,69863,

%U 169034,105365,6352,2,1,45,1297,24600,228613,1016341,1686534,654030,17337,2

%N 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.

%H Sean A. Irvine, <a href="/A300003/b300003.txt">Table of n, a(n) for n = 0..78</a>

%e 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.

%e Triangle begins:

%e 1; (empty permutation, n = 0)

%e 1;

%e 1, 1;

%e 1, 3, 2;

%e 1, 6, 15, 2;

%e 1, 10, 52, 55, 2;

%e 1, 15, 129, 389, 184, 2;

%e The sum of row n is n! since each permutation of length n is accounted for in that row.

%o (Python)

%o def row(n):

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

%o out = [1] if n == 0 else []

%o for k in range(n):

%o r1 = set()

%o out.append(len(frontier))

%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 out

%o print([an for n in range(9) for an in row(n)]) # _Michael S. Branicky_, Jan 26 2023

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

%Y Row sums give A000142.

%K nonn,tabf

%O 0,6

%A _Sean A. Irvine_, Feb 22 2018