A384648 Expansion of (1+2*x+x^2) / (1-x-5*x^2-2*x^3).

1, 3, 9, 26, 77, 225, 662, 1941, 5701, 16730, 49117, 144169, 423214, 1242293, 3646701, 10704594, 31422685, 92239057, 270761670, 794802325, 2333088789, 6848623754, 20103672349, 59012968697, 173228577950, 508500766133, 1492669593277, 4381630579842

Offset

0,2

Comments

Number of walks of length n starting at vertex 0 in the following graph:

1---2

/|\ |

0 | \ |

\| \|

4---3.

Also, by symmetry, the number of walks of length n starting at vertex 4 in the same graph.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Sean A. Irvine, Walks on Graphs.

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

Example

a(2)=9 because we have the walks 3-1-0, 3-1-2, 3-1-3, 3-1-4, 3-2-1, 3-2-3, 3-4-0, 3-4-1, 3-4-3.

Maple

a:= n->  (<<0|1|0|0|1>, <1|0|1|1|1>, <0|1|0|1|0>, <0|1|1|0|1>, <1|1|0|1|0>>^n. <<1, 1, 1, 1, 1>>)[4, 1]:
seq(a(n), n=0..32);

Mathematica

CoefficientList[Series[(1+2*x+x^2) / (1-x-5*x^2-2*x^3), {x, 0, 32}], x]
LinearRecurrence[{1, 5, 2}, {1, 3, 9}, 33] (* Vincenzo Librandi, Oct 14 2025 *)

Prog

(Magma) I:=[1, 3, 9]; [n le 3 select I[n] else Self(n-1) + 5*Self(n-2)+2*Self(n-3): n in [1..35]]; // Vincenzo Librandi, Oct 14 2025

Crossrefs

Cf. A384646 (vertices 0 and 2), A384647 (vertex 1), A077937 (missing edge {1,3}).

Sequence in context: A101169 A119826 A027915 * A295115 A114982 A133405

Adjacent sequences: A384645 A384646 A384647 * A384649 A384650 A384651

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved