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

1, 2, 5, 11, 25, 55, 123, 271, 603, 1331, 2955, 6531, 14483, 32035, 70995, 157107, 348051, 770419, 1706419, 3777779, 8366515, 18523955, 41021619, 90828851, 201134387, 445358643, 986195251, 2183703347, 4835498291, 10707203891, 23709399859, 52499812147

Offset

0,2

Comments

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

3

/|

0-1-2 |

\|

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

Example

a(2)=5 because we have the walk 3-2-1, 3-2-3, 3-2-4, 3-4-2, 3-4-3.

Maple

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

Mathematica

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

Prog

(Magma) I:=[1, 2, 5, 11]; [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. A384598 (vertices 0 and 1), A384599 (vertex 2), A062112 (missing edge {3,4}), A382683 (missing edge {0,1}).

Sequence in context: A172481 A151529 A192922 * A215091 A017919 A017920

Adjacent sequences: A384597 A384598 A384599 * A384601 A384602 A384603

Keyword

nonn,walk,easy

Author

Sean A. Irvine, Jun 04 2025

Status

approved