

A006192


Number of nonintersecting (or selfavoiding) 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


REFERENCES

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163178.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331339.
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), 163178. (Annotated scanned copy)
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Steven R. Finch, SelfAvoiding Walks of a Rook on a Chessboard [From Steven Finch, Apr 20 2019]
Steven R. Finch, SelfAvoiding Walks of a Rook [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Steven R. Finch, Table of NonOverlapping 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(n1)  3*a(n2) + 2*a(n3) + a(n4) with a(0) = 0, a(1) = 1, a(2) = 4 and a(3) = 12.  Henry Bottomley, Sep 05 2001
G.f.: x*(1x^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(n1)3*Self(n2)+2*Self(n3)+Self(n4): n in [1..30]]; // Vincenzo Librandi, Oct 06 2011


CROSSREFS

Cf. A064297, A064298, A007786, A007787, A007764.
Sequence in context: A183159 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



