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
KEYWORD
nonn,tabf
AUTHOR
Sean A. Irvine, Feb 22 2018
STATUS
approved