A094555 Number of walks of length n between two vertices on the same triangular face of a truncated tetrahedron (triangular prism).

0, 1, 1, 6, 11, 46, 111, 386, 1051, 3366, 9671, 29866, 87891, 267086, 794431, 2396946, 7163531, 21545206, 64526391, 193797626, 580955971, 1743741726, 5229477551, 15691927906, 47068793211, 141220360646, 423633119911, 1270955283786

Offset: 0

Author

Paul Barry, May 11 2004

Keywords

• easy
• nonn

Comments

Average of binomial and inverse binomial transforms of the Jacobsthal numbers A001045. - Paul Barry, Jan 04 2005

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).

Crossrefs

Cf. A001045, A094554, A094556.

Programs

Mathematica

LinearRecurrence[{2, 5, -6}, {0, 1, 1, 6}, 30] (* Greg Dresden, Jun 19 2021 *)

PARI

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

Formula

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

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

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

a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*A001045(n-2k). - Paul Barry, Jan 04 2005

E.g.f.: exp(-2*x)*(exp(5*x) + exp(3*x) - exp(2*x) - 1)/6. - Stefano Spezia, Dec 26 2021