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

1, 2, 6, 12, 32, 68, 172, 380, 932, 2108, 5076, 11644, 27732, 64156, 151796, 352956, 831828, 1940060, 4561460, 10658044, 25023764, 58533020, 137311988, 321396540, 753578452, 1764540636, 4136061364, 9687067004, 22702231188, 53178376476, 124613167220

Offset

0,2

Comments

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

0 2

\ /|

1 |

/ \|

4 3.

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,4,-2).

Example

a(3)=6 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-4-1.

Maple

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

Mathematica

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

Prog

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

Crossrefs

Cf. A384604 (vertices 0, 1, 4), A213173 (missing edge {2,3}), A382683 (missing edge {1,4}).

Sequence in context: A163087 A332654 A000650 * A304961 A032178 A102881

Adjacent sequences: A384602 A384603 A384604 * A384606 A384607 A384608

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 04 2025

Status

approved