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
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).
Programs
-
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 *) -
PARI
a(n) = if(n==0, 0, (3^n - 2*(-2)^n - 1)/6) \\ Andrew Howroyd, Jun 15 2021
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