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

1, 3, 8, 22, 58, 158, 420, 1136, 3036, 8180, 21920, 58952, 158168, 425032, 1140976, 3064960, 8229648, 22103600, 59355776, 159410272, 428089760, 1149677536, 3087468096, 8291603712, 22267339200, 59800139584, 160595513856, 431286986880, 1158238963072

Offset

0,2

Comments

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

2

/ \

0-1---3

\ /

4.

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(2)=8 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-1, 3-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>>)[3, 1]:
seq(a(n), n=0..32);

Mathematica

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

Prog

(Magma) I:=[1, 3, 8, 22]; [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 15 2025

Crossrefs

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

Sequence in context: A027243 A110239 A271893 * A001853 A217898 A003227

Adjacent sequences: A384632 A384633 A384634 * A384636 A384637 A384638

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved