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

1, 1, 3, 5, 13, 25, 59, 121, 273, 577, 1275, 2733, 5981, 12905, 28115, 60849, 132289, 286721, 622739, 1350613, 2932109, 6361209, 13806923, 29958441, 65018001, 141086401, 306181963, 664423165, 1441882653, 3128970185, 6790194979, 14735222881, 31976837633

Offset: 0

Author

Sean A. Irvine, Jun 02 2025

Keywords

• nonn
• walk
• easy

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.

Examples

			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.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (1,3,-1).

Crossrefs

Cf. A087640 (walks starting at 2).

Cf. A000079 (missing edge {0,1}), A108411 (missing edge {2,3}), A026581 (adding edge {0,2}), A000244 (K4).

Programs

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] (* or *) CoefficientList[Series[ (1-x^2) / (1-x-3*x^2+x^3),{x,0,32}],x] (* James C. McMahon, Jun 02 2025 *)

Formula

a(n) = A052973(n) + A052973(n-1). a(n) = A087640(n+1) - A087640(n). - R. J. Mathar, Jun 03 2025