OFFSET
0,3
COMMENTS
The number of walks of length n in the 4-vertex graph {{0,1}, {1,2}, {1,3}, {2,3}} starting at vertex 0 (see Example).
Also, a(n+1) is the number of such walks in the same graph starting at vertex 1.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,3,-1).
FORMULA
EXAMPLE
Consider walks starting at 0 in the following graph:
2
/|
0-1 |
\|
3
The 5 walks of length 3 are 0-1-0-1, 0-1-2-1, 0-1-2-3, 0-1-3-1, and 0-1-3-2.
MAPLE
a:= n-> (<<0|1|0>, <0|0|1>, <-1|3|1>>^n. <<1, 1, 3>>)[1, 1]:
seq(a(n), n=0..32); # Alois P. Heinz, Jun 04 2025
MATHEMATICA
LinearRecurrence[{1, 3, -1}, {1, 1, 3}, 33] (* James C. McMahon, Jun 02 2025 *)
(* Alternative: *)
CoefficientList[Series[ (1-x^2) / (1-x-3*x^2+x^3), {x, 0, 32}], x] (* James C. McMahon, Jun 02 2025 *)
PROG
(Magma) m:=35; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x^2) / (1-x-3*x^2+x^3))); // Vincenzo Librandi, Oct 12 2025
CROSSREFS
KEYWORD
nonn,walk,easy
AUTHOR
Sean A. Irvine, Jun 02 2025
STATUS
approved
