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