A384731 Expansion of (1+2*x-x^2) / (1-x-6*x^2+2*x^3).

1, 3, 8, 24, 66, 194, 542, 1574, 4438, 12798, 36278, 104190, 296262, 848846, 2418038, 6918590, 19729126, 56404590, 160942166, 459911454, 1312755270, 3750339662, 10707048374, 30583575806, 87325186726, 249412544814, 712196513558, 2034021408990, 5808375400710

Offset

0,2

Comments

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

1---2

/ \ /|

0 X |

\ / \|

4---3.

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

Example

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

Maple

a:= n-> (<<0|1|0|0|1>, <1|0|1|1|0>, <0|1|0|1|1>, <0|1|1|0|1>, <1|0|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-x-6*x^2+2*x^3), {x, 0, 32}], x]
LinearRecurrence[{1, 6, -2}, {1, 3, 8}, 40] (* Harvey P. Dale, Jul 30 2025 *)

Crossrefs

Cf. A384730 (vertex 0), A384732 (vertices 2 and 3).

Sequence in context: A096886 A176904 A056332 * A091588 A297219 A018046

Adjacent sequences: A384728 A384729 A384730 * A384732 A384733 A384734

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved