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

1, 1, 3, 7, 19, 49, 131, 343, 911, 2397, 6347, 16735, 44251, 116785, 308611, 814815, 2152583, 5684477, 15015355, 39655527, 104742659, 276635985, 730663043, 1929789255, 5096983167, 13461994429, 35555794923, 93909205391, 248032219243, 655098462417, 1730238763395

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 (1,5,-1,-2).

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

Cf. A384641 (vertex 2), A384642 (vertex 3), A005824 (missing edge {2,4}), A026597 (missing edge {0,1}).

Sequence in context: A017926 A017927 A116903 * A298416 A395895 A151266

Adjacent sequences: A384637 A384638 A384639 * A384641 A384642 A384643

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved