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

1, 4, 12, 42, 136, 458, 1512, 5042, 16728, 55642, 184840, 614434, 2041784, 6786058, 22552168, 74951058, 249090840, 827832634, 2751217352, 9143416194, 30387253880, 100989154026, 335627745064, 1115426752498, 3707013922264, 12319906116890, 40944028340104

Offset

0,2

Comments

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

1---2

/|\ /|

0 | X |

\|/ \|

4---3.

Also, by symmetry, the number of walks of length n starting at 4 in the same graph.

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Sean A. Irvine, Walks on Graphs.

Index entries for linear recurrences with constant coefficients, signature (2,5,-2).

Example

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

Maple

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

Mathematica

CoefficientList[Series[(1+2*x-x^2) / (1-2*x-5*x^2+2*x^3), {x, 0, 32}], x]
LinearRecurrence[{2, 5, -2}, {1, 4, 12}, 30] (* Harvey P. Dale, Aug 30 2025 *)

Crossrefs

Cf. A384671 (vertex 0), A384673 (vertices 2 and 3), A384646 (missing edge {2,4}).

Sequence in context: A300124 A343517 A308371 * A052303 A017942 A149344

Adjacent sequences: A384669 A384670 A384671 * A384673 A384674 A384675

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved