A052899 Expansion of g.f.: (1-2*x) / ((x-1)*(4*x^2+2*x-1)).

1, 1, 5, 13, 45, 141, 461, 1485, 4813, 15565, 50381, 163021, 527565, 1707213, 5524685, 17878221, 57855181, 187223245, 605867213, 1960627405, 6344723661, 20531956941, 66442808525, 215013444813, 695798123725, 2251650026701, 7286492548301, 23579585203405, 76305140600013

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

From L. Edson Jeffery, Apr 19 2011: (Start)

Let A be the unit-primitive matrix (see [Jeffery])

A = A_(10,4) =

(0 0 0 0 1)

(0 0 0 2 0)

(0 0 2 0 1)

(0 2 0 2 0)

(2 0 2 0 1).

Then a(n) = (1/5)*trace(A^n). (End)

a(n-1)+1 is the number of paths to reach a position outside a 4 X 4 chessboard after n steps, starting in one of the corners, when performing a walk with unit steps on the square lattice. - Ruediger Jehn, Oct 10 2024

Links

• Harvey P. Dale, Table of n, a(n) for n = 0..1000
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 875
• L. E. Jeffery, Unit-primitive matrices
• Index entries for linear recurrences with constant coefficients, signature (3,2,-4).

Crossrefs

Cf. A084057.

Programs

Magma

[(1/5)*(2^(n+1)*Lucas(n)+1): n in [0..50]]; // Vincenzo Librandi, Apr 20 2011

Maple

spec := [S,{S=Sequence(Prod(Union(Sequence(Union(Z,Z)),Z,Z),Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

Mathematica

CoefficientList[Series[(1-2x)/((x-1)(4x^2+2x-1)),{x,0,40}],x] (* or *) LinearRecurrence[{3,2,-4},{1,1,5},40] (* Harvey P. Dale, Jul 10 2017 *)

Maxima

makelist(coeff(taylor((1-2*x)/(1-3*x-2*x^2+4*x^3),x,0,n),x,n),n,0,25); /* Bruno Berselli, May 30 2011 */

Sage

from sage.combinat.sloane_functions import recur_gen2b
it = recur_gen2b(1,1,2,4, lambda n:-1)
[next(it) for i in range(1,28)] # Zerinvary Lajos, Jul 09 2008

Formula

Recurrence: {a(1)=1, a(0)=1, -4*a(n) - 2*a(n+1) + a(n+2) + 1 = 0}.

a(n) = Sum((-1/25)*(-1-8*_alpha+4*_alpha^2)*_alpha^(-1-n), _alpha=RootOf(1-3*_Z-2*_Z^2+4*_Z^3)).

a(n)/a(n-1) tends to (1 + sqrt(5)) = 3.236067... - Gary W. Adamson, Mar 01 2008

a(n) = (1/5) * Sum_{k=1..5} ((x_k)^4-3*(x_k)^2+1), x_k=2*cos((2*k-1)*Pi/10). Also, a(n)/a(n-1) -> spectral radius of matrix A_(10,4) above. - L. Edson Jeffery, Apr 19 2011

a(n) = (2*A087131(n)+1)/5. - Bruno Berselli, Apr 20 2011

a(n) = (2/5)*((1+sqrt(5))^n + (1-sqrt(5))^n + 1/2). - Ruediger Jehn, Sep 29 2024

E.g.f.: exp(x)*(1 + 4*cosh(sqrt(5)*x))/5. - Stefano Spezia, Oct 02 2024

Extensions

More terms from James Sellers, Jun 08 2000