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

2, 8, 60, 816, 17520, 550080, 23839200, 1365799680, 100053999360, 9127781913600, 1015061950425600, 135193044668774400, 21248464632595200000, 3891825697262043340800, 821745573997874093568000, 198152975926832672858112000, 54121124248225908770856960000, 16621698830590738881776812032000

Offset: 1

Author

Hugo van der Sanden, Jul 22 2004

Keywords

• nonn
• easy
• walk

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

Examples

			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.
		

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

Crossrefs

Column 2 of A269565.

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

Programs

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 *)

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

Extensions

a(16)-a(18) from Stefano Spezia, Jul 19 2024