[seqfan] Sequences for gaps in permutations

[Jay Anderson]

As part of looking at the pancake problem (sorting by prefix reversals) a
common
heuristic for solving with some sort of a* search is to count the number of
gaps
in the permutation. Elements of this triangle T(n,k) = number of
permutations of
length n with k gaps between adjacent elements.

 1: 1
 2: 2
 3: 2 4
 4: 2 10 10 2
 5: 2 16 48 40 14
 6: 2 22 120 256 230 90
 7: 2 28 226 888 1670 1580 646
 8: 2 34 366 2198 7198 12846 12434 5242
 9: 2 40 540 4448 22120 64968 112820 110320 47622
10: 2 46 748 7900 54304 236968 650644 1108612 1090270 479306
11: 2 52 990 12816 114180 685368 2732268 7165200 12032154 11876980 5296790
12: 2 58 1266 19458 214740 1674468 9086628 33940644 86059242 142852450
141373610 63779034

This is essentially A001100 with each row reversed. Here are the length 4
permutations listed with the number of gaps:

[1, 2, 3, 4] - 0
[4, 3, 2, 1] - 0

[1, 2, 4, 3] - 1
[4, 1, 2, 3] - 1
[1, 4, 3, 2] - 1
[3, 4, 1, 2] - 1
[4, 3, 1, 2] - 1
[3, 4, 2, 1] - 1
[3, 2, 1, 4] - 1
[2, 3, 4, 1] - 1
[2, 1, 4, 3] - 1
[2, 1, 3, 4] - 1

[1, 4, 2, 3] - 2
[4, 1, 3, 2] - 2
[1, 3, 4, 2] - 2
[1, 3, 2, 4] - 2
[3, 1, 2, 4] - 2
[3, 2, 4, 1] - 2
[2, 3, 1, 4] - 2
[2, 4, 3, 1] - 2
[4, 2, 3, 1] - 2
[4, 2, 1, 3] - 2

[3, 1, 4, 2] - 3
[2, 4, 1, 3] - 3

For the pancake problem heuristic we actually want to count an extra gap
when
the last element isn't in place. That is we also need check the space
between
the bottom pancake and the plate for a gap. That gives this triangle
sequence:

 1: 1
 2: 1 1
 3: 1 2 3
 4: 1 3 11 7 2
 5: 1 4 24 44 35 12
 6: 1 5 42 140 247 207 78
 7: 1 6 65 324 995 1630 1451 568
 8: 1 7 93 625 2869 7833 12667 11551 4674
 9: 1 8 126 1072 6692 27084 69802 111704 103443 42948
10: 1 9 164 1694 13520 74696 279686 692546 1100351 1029775 436358
11: 1 10 207 2520 24642 175356 890358 3145128 7573005 11961578 11283563
4860432
12: 1 11 255 3579 41580 365454 2389470 11341398 38368521 90447815 142174435
134950479 58918602

Here are the length 4 permutations listed with the number of gaps:

[1, 2, 3, 4] - 0

[4, 3, 2, 1] - 1
[3, 2, 1, 4] - 1
[2, 1, 3, 4] - 1

[1, 2, 4, 3] - 2
[4, 1, 2, 3] - 2
[1, 4, 3, 2] - 2
[1, 3, 2, 4] - 2
[3, 1, 2, 4] - 2
[3, 4, 1, 2] - 2
[4, 3, 1, 2] - 2
[3, 4, 2, 1] - 2
[2, 3, 1, 4] - 2
[2, 3, 4, 1] - 2
[2, 1, 4, 3] - 2

[1, 4, 2, 3] - 3
[4, 1, 3, 2] - 3
[1, 3, 4, 2] - 3
[3, 2, 4, 1] - 3
[2, 4, 3, 1] - 3
[4, 2, 3, 1] - 3
[4, 2, 1, 3] - 3

[3, 1, 4, 2] - 4
[2, 4, 1, 3] - 4

I was not able to find this sequence in OEIS (let me know if I missed it).
The initial columns appear to be
(with some offsets):

T(n,0) = 1 => A000012
T(n,1) = n => A000027
T(n,2) = 1/2(5n^2 + n) => A005475
T(n,3) = 1/6(29n^3 + 3n^2 + 10n)

That's as far as I've gone looking at it. It seems like it be an interesting
addition to OEIS.

-----Jay Anderson