A181394 Summed lengths of all nonintersecting rook paths on a 3 x n board.

2, 14, 64, 284, 1206, 4882, 19060, 72588, 271548, 1001964, 3656480, 13223348, 47461350, 169263658, 600355808, 2119297852, 7450253362, 26095036854, 91102304600, 317127751352, 1101029901244, 3813576283628, 13180379580636, 45463936339816

Offset

1,1

Comments

Paths are self-avoiding from one corner to the diagonally opposite corner.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (8,-22,28,-23,4,2,-4,-1).

Formula

G.f.: 2*x*(1 - x - 2*x^2 + 12*x^3 - 2*x^4 + 2*x^5 - 2*x^6)/((1 - x + x^2)^2*(1 - 3*x - x^2)^2). - Alois P. Heinz, Nov 26 2010, modified Andrew Howroyd, Jan 06 2020

Asymptotics: a(n) ~ ((3/4-sqrt(13)/52)*n-1/4-sqrt(13)/52)*((sqrt(13)+3)/2)^n. - Vaclav Kotesovec, Aug 31 2012

Example

E.g. s(2) {RRD, DRR, RDR, DRURD} 3+3+3+5 = 14.

Maple

a:= n-> (Matrix(8, (i, j)->if i+1=j then 1 elif i=8 then [-1, -4, 2, 4, -23, 28, -22, 8][j] else 0 fi)^n. <<0, 2, 14, 64, 284, 1206, 4882, 19060>>)[1, 1]: seq (a(n), n=1..24);  # Alois P. Heinz, Nov 26 2010

Mathematica

LinearRecurrence[{8, -22, 28, -23, 4, 2, -4, -1}, {2, 14, 64, 284, 1206, 4882, 19060, 72588}, 24] (* Jean-François Alcover, Jan 03 2022 *)

Crossrefs

Enumeration of these paths is A006192, related sequences A181395, A181396, A181397, A181398, A181399.

Sequence in context: A362157 A167555 A222445 * A335630 A266590 A196977

Adjacent sequences: A181391 A181392 A181393 * A181395 A181396 A181397

Keyword

nonn,walk

Author

David Scambler, Oct 17 2010

Extensions

More terms from Alois P. Heinz, Nov 26 2010

Status

approved