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

1, 3, 10, 30, 94, 288, 892, 2748, 8488, 26184, 80824, 249408, 769744, 2375472, 7331104, 22624608, 69822688, 215481600, 665004736, 2052290496, 6333636736, 19546425984, 60322817920, 186164066304, 574526552320, 1773063734016, 5471905544704, 16887012920832

Offset

0,2

Comments

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

2

/|\

0-1-+-3

\|/

4.

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

Example

a(2)=10 because we have the walks 2-1-0, 2-1-2, 2-1-3, 2-1-4, 2-3-1, 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|1|1>, <0|1|0|1|1>, <0|1|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+x) / (1-2*x-4*x^2+2*x^3), {x, 0, 32}], x]
LinearRecurrence[{2, 4, -2}, {1, 3, 10}, 30] (* Harvey P. Dale, Jul 07 2025 *)

Crossrefs

Cf. A384677 (vertices 0 and 1), A000244 (missing edge {0,1}), A384633 (missing edge {2,4}), A384640 (missing edge {1,3}).

Sequence in context: A269800 A033113 A360714 * A290718 A300421 A302289

Adjacent sequences: A384675 A384676 A384677 * A384679 A384680 A384681

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved