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