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