Up/Down/Left/Right Permutation

[hv at crypt.org]

hv at crypt.org wrote:
:%S A096121 2,8,60,816,17520,550080,23839200,1365799680,100053999360
:%T A096121 9127781913600,1015061950425600,135193044668774400
:%U A096121 21248464632595200000,3891825697262043340800,821745573997874093568000
:%N A096121 Full spectrum rook's walks on a (2 x n) board
:%D A096121 A rook must land on each square exactly once, but may start and end anywhere and may intersect it's own path. Inspired by Leroy Quet in a 2004/7/5 posting to the Seqfan mailing list.
:%e A096121 Tagging the squares on a (3 x 2) board with A,B,C/D,E,F, the 10 tours starting at A are: ABCFDE, ABCFED, ABEDFC, ACBEDF, ACBEFD, ACFDEB, ADEBCF, ADEFCB, ADFCBE, ADFEBC. There are a similar 10 tours starting at each of the other 5 squares, so a(3) = 6 * 10 = 60.
:%Y A096121 Cf. A096970 and references to "rook tours" or "rook walks"
:%K A096121 nonn,easy,walk
:%O A096121 1,1
:%A A096121 hv at crypt.org (Hugo van der Sanden)
:%F A096121 a(n+1)=n(n+1)(a(n) + a(n-1)) for n > 1

Further refinement gives me:
  a(n + 1) = 2(n + 1)! sum_{k = 0}^{floor(n / 2)} {
      perm(n - k, k    ) . comb(n - k    , k)
    + perm(n - k, k + 1) . comb(n - 1 - k, i)
  }

(.. where perm(a,b) == a!/b!; comb(a,b) == a!/b!/(a-b)!).

Hugo van der Sanden