A094556 Number of walks of length n between opposite vertices on a triangular prism.

0, 1, 0, 7, 8, 51, 100, 407, 1008, 3451, 9500, 30207, 87208, 268451, 791700, 2402407, 7152608, 21567051, 64482700, 193885007, 580781208, 1744091251, 5228778500, 15693326007, 47065997008, 141225953051, 423621935100, 1270977653407

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 3.

Index entries for linear recurrences with constant coefficients, signature (2,5,-6).

Formula

G.f.: x*(1 - 2*x + 2*x^2)/((1 - x)*(1 + 2*x)*(1 - 3*x)).

a(n) = 3^n/6 - (-2)^n/3 - 1/6 + 0^n/3.

a(n) = 2*a(n-1) + 5*a(n-2) - 6*a(n-3) for n >= 4.

E.g.f.: exp(-x)*(2+exp(3*x))*sinh(x)/3. - Stefano Spezia, Sep 26 2023

Mathematica

LinearRecurrence[{2, 5, -6}, {0, 1, 0, 7}, 30] (* or *) CoefficientList[ Series[ x (1-2x+2x^2)/((1-x)(1+2x)(1-3x)), {x, 0, 30}], x] (* Harvey P. Dale, Jul 13 2011 *)

Prog

(PARI) a(n) = if(n==0, 0, (3^n - 2*(-2)^n - 1)/6) \\ Andrew Howroyd, Jun 15 2021

Crossrefs

Cf. A094554, A094555.

Sequence in context: A038274 A201919 A249310 * A249329 A041023 A041108

Adjacent sequences: A094553 A094554 A094555 * A094557 A094558 A094559

Keyword

easy,nonn

Author

Paul Barry, May 11 2004

Status

approved