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

1, 1, 2, 4, 8, 18, 38, 86, 186, 418, 914, 2042, 4490, 9994, 22042, 48954, 108154, 239898, 530522, 1175898, 2601882, 5764634, 12759322, 28262298, 62566554, 138567834, 306790810, 679404442, 1504298906, 3331199386, 7376004506, 16333395354, 36166416794

Offset

0,3

Comments

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

3

/|

0-1-2 |

\|

4.

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

Example

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

Maple

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-2|-2|4|1>>^n. <<1, 1, 2, 4>>)[1, 1]:
seq(a(n), n=0..32);  # Alois P. Heinz, Jun 04 2025

Mathematica

CoefficientList[Series[(1 - 3*x^2)/(1 - x - 4*x^2 + 2*x^3 + 2*x^4), {x, 0, 32}], x] (* Michael De Vlieger, Jun 04 2025 *)
LinearRecurrence[{1, 4, -2, -2}, {1, 1, 2, 4}, 33] (* Vincenzo Librandi, Oct 13 2025 *)

Prog

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

Crossrefs

Cf. A384599 (vertex 2), A384600 (vertex 3), A062112 (missing edge {3,4}), A382683 (missing edge {0,1}).

Sequence in context: A288206 A371791 A218078 * A110110 A300221 A233437

Adjacent sequences: A384595 A384596 A384597 * A384599 A384600 A384601

Keyword

nonn,walk,easy

Author

Sean A. Irvine, Jun 04 2025

Status

approved