[go: up one dir, main page]

login
A006192
Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of 3 X n board.
(Formerly M3453)
7
1, 4, 12, 38, 125, 414, 1369, 4522, 14934, 49322, 162899, 538020, 1776961, 5868904, 19383672, 64019918, 211443425, 698350194, 2306494009, 7617832222, 25159990674, 83097804242, 274453403399, 906458014440
OFFSET
1,2
REFERENCES
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331-339.
Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
Steven R. Finch, Self-Avoiding Walks of a Rook on a Chessboard [From Steven Finch, Apr 20 2019]
Steven R. Finch, Self-Avoiding Walks of a Rook [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Steven R. Finch, Table of Non-Overlapping Rook Paths [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, Emails, 1994
FORMULA
a(n) = 4*a(n-1) - 3*a(n-2) + 2*a(n-3) + a(n-4) with a(0) = 0, a(1) = 1, a(2) = 4 and a(3) = 12. - Henry Bottomley, Sep 05 2001
G.f.: x*(1-x^2)/(1 - 4*x + 3*x^2 - 2*x^3 - x^4). - Emeric Deutsch, Dec 22 2004
MATHEMATICA
LinearRecurrence[{4, -3, 2, 1}, {1, 4, 12, 38}, 40] (* Harvey P. Dale, Oct 05 2011 *)
PROG
(Magma) I:=[1, 4, 12, 38]; [n le 4 select I[n] else 4*Self(n-1)-3*Self(n-2)+2*Self(n-3)+Self(n-4): n in [1..30]]; // Vincenzo Librandi, Oct 06 2011
CROSSREFS
KEYWORD
nonn,walk,nice,easy
STATUS
approved