A096121 - OEIS

%I #40 Jul 20 2024 14:42:31

%S 2,8,60,816,17520,550080,23839200,1365799680,100053999360,

%T 9127781913600,1015061950425600,135193044668774400,

%U 21248464632595200000,3891825697262043340800,821745573997874093568000,198152975926832672858112000,54121124248225908770856960000,16621698830590738881776812032000

%N Number of full spectrum rook's walks on a (2 X n) board.

%C A rook must land on each square exactly once, but may start and end anywhere and may intersect its own path.

%C This also gives the number of ways to arrange n pairs of shoes in a row so that no left shoe is next to a right shoe from a different pair. - _Jerrold Grossman_, Jul 19 2024

%D Inspired by _Leroy Quet_ in a Jul 05 2004 posting to the Seqfan mailing list.

%H Y. Cha, <a href="http://purl.flvc.org/fsu/fd/FSU_migr_etd-3960">Closed form solutions of difference equations</a> (2011) PhD Thesis, Florida State University, Example 5.1.1

%F D-finite with recurrence: a(n+1) = n*(n+1)*(a(n) + a(n-1)) for n > 1.

%F Further refinement gives: a(n+1) = 2*(n+1)! * Sum_{k=0..floor(n/2)} (P(n-k, k) * C(n-k, k) + P(n-k, k+1) * C(n-1-k, i)), where P(i,j) = i!/j!.

%F Conjecture: a(n) = 2*n!*A102038(n). - _Mikhail Kurkov_, Feb 07 2019

%e 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.

%t a[1]=2; a[2]=8; a[n_]:= n*(n-1)*(a[n-1] + a[n-2]); Array[a,18] (* _Stefano Spezia_, Jul 19 2024 *)

%Y Column 2 of A269565.

%Y Cf. A096970 and references to "rook tours" or "rook walks".

%K nonn,easy,walk

%O 1,1

%A _Hugo van der Sanden_, Jul 22 2004

%E a(16)-a(18) from _Stefano Spezia_, Jul 19 2024