A006192 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of 3 X n board.
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
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).
Programs
-
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
-
Mathematica
LinearRecurrence[{4,-3,2,1},{1,4,12,38},40] (* Harvey P. Dale, Oct 05 2011 *)
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