A094554 Number of closed walks of length n at a base vertex of a truncated tetrahedron (triangular prism).

1, 0, 3, 2, 19, 30, 143, 322, 1179, 3110, 10183, 28842, 89939, 262990, 802623, 2380562, 7196299, 21479670, 64657463, 193535482, 581480259, 1742693150, 5231574703, 15687733602, 47077181819, 141203583430, 423666674343

Offset: 0

Author

Paul Barry, May 11 2004

Keywords

• easy
• nonn

Comments

For n > 0, 6*a(n) is the number of 3-colorings of the prism of size 2 X n (i.e., C_2 X C_n).More generally, the number of k-colorings of the prism of size 2 X n is given by (k^2 - 3*k + 3)^n + (k - 1) * ((3 - k)^n + (1 - k)^n) + k^2 - 3*k + 1 (chromatic polynomial). - Sela Fried, Oct 07 2023

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• N. L. Biggs, R. M. Damerell, and D. A. Sands, Recursive families of graphs, Journal of Combinatorial Theory Series B Volume 12 (1972), 123-131.
• 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. A002001, A025192, A094555, A094556, A328778.

Programs

Mathematica

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

PARI

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

Formula

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

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

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

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