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

1, 2, 6, 12, 30, 66, 156, 354, 822, 1884, 4350, 10002, 23052, 53058, 122214, 281388, 648030, 1492194, 3436284, 7912866, 18221718, 41960316, 96625470, 222506418, 512382828, 1179902082, 2717050566, 6256756812, 14407908510, 33178178946, 76401904476, 175936441314

Offset

0,2

Comments

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

0-1

|\

| 2

|/

4-3.

Links

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

Sean A. Irvine, Walks on Graphs.

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

Cf. A105476 (vertices 0, 1), A382683 (missing edge {4,3}).

Sequence in context: A182863 A161507 A335711 * A032177 A095349 A385189

Adjacent sequences: A384611 A384612 A384613 * A384615 A384616 A384617

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 04 2025

Status

approved