[seqfan] Permutations with Windowed Affinity

[Ron Hardin]

Permutations of 0..n-1 that put elements that start close together, close together at the end.

Shift initial 0..n-1 by as much as +-k in the permutation.
In each consecutive 3 elements, the maximum-minimum is 3 or less.
A couple of things are surprising -
1.  Every column of T(n,k) has the same recurrence albeit with a different lower limit
2.  plateaus in the rows of T(n,k)
I have yet to try what windows and limits other than 3 produce.

/tmp/fde
T(n,k)=Number of length n arrays of permutations of 0..n-1 with each element moved by -k to k places and every three consecutive elements having its maximum within 3 of its minimum

Table starts
....1....1....1....1...1...1...1...1...1...1...1..1..1..1..1..1.1.1.1
....2....2....2....2...2...2...2...2...2...2...2..2..2..2..2..2.2.2..
....3....6....6....6...6...6...6...6...6...6...6..6..6..6..6..6.6....
....5...14...24...24..24..24..24..24..24..24..24.24.24.24.24.24......
....7...14...18...36..36..36..36..36..36..36..36.36.36.36.36.........
...11...16...18...20..36..36..36..36..36..36..36.36.36.36............
...16...22...24...24..27..48..48..48..48..48..48.48.48...............
...25...36...40...40..40..49..80..80..80..80..80.80..................
...37...56...64...64..64..64..76.128.128.128.128.....................
...57...85..100..100.100.100.100.120.200.200.........................
...85..125..144..144.144.144.144.144.168.............................
..130..189..216..216.216.216.216.216.................................
..195..285..324..324.324.324.324.....................................
..297..434..496..496.496.496.........................................
..447..655..748..748.748.............................................
..679..993.1136.1136.................................................
.1024.1499.1712......................................................
.1553.2271...........................................................
.2345................................................................

Column 1 is A130137(n-1)

Empirical for column k:
k=1: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4)
k=2: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>12
k=3: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>12
k=4: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>12
k=5: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>12
k=6: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>12
k=7: a(n)=a(n-1)+a(n-2)-a(n-3)+a(n-4) for n>13

Some.solutions.for.n=7.k=4..
..1....0....0....3....1....0....0....0....0....0....0....0....1....0....1....2..
..0....2....1....0....0....1....1....1....1....2....1....2....0....1....0....0..
..2....1....2....1....3....2....2....2....2....1....2....1....2....2....3....1..
..3....3....3....2....2....4....3....4....3....3....4....4....3....4....2....3..
..4....4....4....4....4....3....5....5....4....4....3....3....5....5....5....4..
..6....5....6....5....5....6....4....6....5....6....5....6....6....3....4....6..
..5....6....5....6....6....5....6....3....6....5....6....5....4....6....6....5..
 rhhardin at mindspring.com rhhardin at att.net (either)