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
Examples
E.g. s(2) {RRD, DRR, RDR, DRURD} 3+3+3+5 = 14.
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).
Crossrefs
Programs
-
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 *)
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
Extensions
More terms from Alois P. Heinz, Nov 26 2010
Comments