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.
Original entry on oeis.org
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
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.
-
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
A007972
Number of permutations that are 2 "block reversals" away from 12...n.
Original entry on oeis.org
2, 15, 52, 129, 266, 487, 820, 1297, 1954, 2831, 3972, 5425, 7242, 9479, 12196, 15457, 19330, 23887, 29204, 35361, 42442, 50535, 59732, 70129, 81826, 94927, 109540, 125777, 143754, 163591, 185412, 209345, 235522, 264079, 295156, 328897, 365450, 404967, 447604
Offset: 3
-
a[n_] := Block[{s, allb, r = Flatten[Table[{i, j}, {i, n}, {j, i + 1, n}], 1]}, allb[pp_] := Union@ Table[ s=pp; s[[Range @@ e]] = Reverse[ s[[ Range @@ e]]]; s, {e, r}]; Length[Flatten[allb /@ allb[Range[n]], 1] // Union] - 1]; a /@ Range[3,15] (* Giovanni Resta, Jun 08 2015 *)
A007973
Number of permutations that are n-2 "block reversals" away from 12...n.
Original entry on oeis.org
1, 3, 15, 55, 184, 648, 2111, 6352, 17337, 42878, 102050, 239756, 562728
Offset: 2
-
def a(n):
perm = tuple(range(1, n+1)); reach = {perm}; frontier = {perm}
for k in range(n-2):
r1 = set()
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 len(frontier)
print([a(n) for n in range(2, 10)]) # Michael S. Branicky, Jan 26 2023
A007974
Number of permutations that are n-3 "block reversals" away from 12...n.
Original entry on oeis.org
1, 6, 52, 389, 2539, 16604, 105365, 654030, 3900116, 22073230, 116855950, 567965207
Offset: 3
-
def a(n):
perm = tuple(range(1, n+1)); reach = {perm}; frontier = {perm}
for k in range(n-3):
r1 = set()
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 len(frontier)
print([a(n) for n in range(3, 10)]) # Michael S. Branicky, Jan 26 2023
Showing 1-4 of 4 results.