A006192 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of 3 X n board. (Formerly M3453)

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

Vincenzo Librandi, Table of n, a(n) for n = 1..150

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

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

Index entries for linear recurrences with constant coefficients, signature (4,-3,2,1).

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

Cf. A064297, A064298, A007786, A007787, A007764.

Sequence in context: A369682 A289809 A014345 * A354341 A149324 A149325

Adjacent sequences: A006189 A006190 A006191 * A006193 A006194 A006195

Keyword

nonn,walk,nice,easy

Author

N. J. A. Sloane

Status

approved