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

1, 1, 2, 4, 8, 18, 38, 86, 186, 418, 914, 2042, 4490, 9994, 22042, 48954, 108154, 239898, 530522, 1175898, 2601882, 5764634, 12759322, 28262298, 62566554, 138567834, 306790810, 679404442, 1504298906, 3331199386, 7376004506, 16333395354, 36166416794

Offset: 0

Author

Sean A. Irvine, Jun 04 2025

Keywords

• nonn
• walk
• easy

Comments

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

3

/|

0-1-2 |

\|

4.

Also, for n>=1, the number of walks of length n-1 starting from vertex 1 in the same graph.

Examples

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

Links

• Sean A. Irvine, Walks on Graphs.
• Index entries for linear recurrences with constant coefficients, signature (1,4,-2,-2).

Crossrefs

Cf. A384599 (vertex 2), A384600 (vertex 3), A062112 (missing edge {3,4}), A382683 (missing edge {0,1}).

Programs

Maple

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

Mathematica

CoefficientList[Series[(1 - 3*x^2)/(1 - x - 4*x^2 + 2*x^3 + 2*x^4), {x, 0, 32}], x] (* Michael De Vlieger, Jun 04 2025 *)