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

1, 3, 8, 21, 56, 147, 390, 1027, 2718, 7169, 18952, 50025, 132180, 349015, 921986, 2434831, 6431386, 16985525, 44863652, 118490229, 312960192, 826576635, 2183160062, 5766102587, 15229405878, 40223605481, 106238212160, 280594628513, 741103272076, 1957390991519

Offset

0,2

Comments

Number of walks of length n starting at vertex 2 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 (1,5,-1,-2).

Example

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

Mathematica

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

Prog

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

Crossrefs

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

Sequence in context: A001671 A360054 A309226 * A278616 A278615 A090413

Adjacent sequences: A384638 A384639 A384640 * A384642 A384643 A384644

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved