A007786 Number of nonintersecting rook paths joining opposite corners of 4 X n board.

1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866, 809563548, 4438573234, 24335048679, 133419610132, 731487691902, 4010463268476, 21987818897998, 120550710615560, 660932932108467

Offset

1,2

References

Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).

Links

Harvey P. Dale, Table of n, a(n) for n = 1..1000

F. Faase, Counting Hamiltonian cycles in product graphs

F. Faase, Results from the counting program

F. Faase, Rook path problem

D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, Emails, 1994

Index entries for linear recurrences with constant coefficients, signature (12,-54,124,-133,-16,175,-94,-69,40,12,-4,-1).

Formula

a(n) = 12*a(n - 1) - 54*a(n - 2) + 124*a(n - 3) - 133*a(n - 4) - 16*a(n - 5) + 175*a(n - 6) - 94*a(n - 7) - 69*a(n - 8) + 40*a(n - 9) + 12*a(n - 10) - 4*a(n - 11) - a(n - 12). - Vladeta Jovovic, Mar 20 2000

G.f.: x*(x^10-15*x^8+6*x^7+50*x^6-26*x^5-39*x^4+36*x^3-4*x^2-4*x+1) / ((x^6+2*x^5-9*x^4-5*x^3+15*x^2-8*x+1)*(x^6+2*x^5-7*x^4-3*x^3+7*x^2-4*x+1)). [Colin Barker, Nov 24 2012]

Mathematica

LinearRecurrence[{12, -54, 124, -133, -16, 175, -94, -69, 40, 12, -4, -1}, {1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866}, 30] (* Harvey P. Dale, Jun 27 2012 *)

Crossrefs

Row 4 of A064298.

Cf. A006192, A007764, A007787.

Sequence in context: A197338 A214931 A229366 * A026662 A196074 A329172

Adjacent sequences: A007783 A007784 A007785 * A007787 A007788 A007789

Keyword

nonn,easy,nice,walk

Author

Heiner Marxen

Extensions

More terms from Vladeta Jovovic, Mar 20 2000

Status

approved