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

1, 4, 10, 32, 90, 270, 784, 2314, 6774, 19912, 58410, 171518, 503392, 1477802, 4337798, 12733592, 37378186, 109721742, 322079856, 945444938, 2775287702, 8146672104, 23914000490, 70197936414, 206061283072, 604878966122, 1775581254310, 5212098651064

Offset

0,2

Comments

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

1---2

/|\ |

0 | \ |

\| \|

4---3.

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

Example

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

Maple

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

Mathematica

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

Prog

(Magma) I:=[1, 4, 10]; [n le 3 select I[n] else Self(n-1) + 5*Self(n-2)+2*Self(n-3): n in [1..35]]; // Vincenzo Librandi, Oct 14 2025

Crossrefs

Cf. A384646 (vertices 0, 2), A384648 (vertices 3 and 4), A077937 (missing edge {1,3}).

Sequence in context: A015796 A318562 A034717 * A295404 A001673 A017936

Adjacent sequences: A384644 A384645 A384646 * A384648 A384649 A384650

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 05 2025

Status

approved