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,3

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

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

Mathematica

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

Prog

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

Crossrefs

Cf. A002001, A025192, A094555, A094556, A328778.

Sequence in context: A033668 A030239 A040308 * A077810 A232505 A297939

Sequence in context: A032448 A066195 A090587 * A223881 A206582 A154262

Adjacent sequences: A094551 A094552 A094553 * A094555 A094556 A094557

Keyword

easy,nonn

Author

Paul Barry, May 11 2004

Status

approved