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
KEYWORD
nonn,walk
AUTHOR
David Scambler, Oct 17 2010
EXTENSIONS
More terms from Alois P. Heinz, Nov 26 2010
STATUS
approved