|
|
A096121
|
|
Number of full spectrum rook's walks on a (2 X n) board.
|
|
3
|
|
|
2, 8, 60, 816, 17520, 550080, 23839200, 1365799680, 100053999360, 9127781913600, 1015061950425600, 135193044668774400, 21248464632595200000, 3891825697262043340800, 821745573997874093568000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
REFERENCES
|
Inspired by Leroy Quet in a Jul 05 2004 posting to the Seqfan mailing list.
|
|
LINKS
|
|
|
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!.
|
|
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.
|
|
CROSSREFS
|
Cf. A096970 and references to "rook tours" or "rook walks".
|
|
KEYWORD
|
nonn,easy,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|