A384633 Expansion of (1+x-2*x^2-2*x^3) / (1-6*x^2-4*x^3+2*x^4).

1, 1, 4, 8, 26, 62, 180, 460, 1276, 3356, 9136, 24320, 65688, 175752, 473136, 1268624, 3410448, 9152784, 24590912, 66021248, 177335712, 476185568, 1278917440, 3434413760, 9223575488, 24769781184, 66521273088, 178644161536, 479759612288, 1288410499200

Offset

0,3

Comments

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

2

/ \

0-1---3

\ /

4.

Also, for n>=1, the number of walks of length n-1 starting at vertex 1 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 (0,6,4,-2).

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

Cf. A384634 (vertices 2, 4), A384635 (vertex 3), A005824 (missing edge {1,3}), A105476 (missing edge {1,2}).

Sequence in context: A126733 A297695 A333894 * A218079 A012982 A012952

Adjacent sequences: A384630 A384631 A384632 * A384634 A384635 A384636

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved