OFFSET
1,1
COMMENTS
A rook must land on each square exactly once, but may start and end anywhere and may intersect its own path.
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
REFERENCES
Inspired by Leroy Quet in a Jul 05 2004 posting to the Seqfan mailing list.
LINKS
Y. Cha, Closed form solutions of difference equations (2011) PhD Thesis, Florida State University, Example 5.1.1
FORMULA
D-finite with recurrence: a(n+1) = n*(n+1)*(a(n) + a(n-1)) for n > 1.
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!.
Conjecture: a(n) = 2*n!*A102038(n). - Mikhail Kurkov, Feb 07 2019
EXAMPLE
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.
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,easy,walk
AUTHOR
Hugo van der Sanden, Jul 22 2004
EXTENSIONS
a(16)-a(18) from Stefano Spezia, Jul 19 2024
STATUS
approved