A384711 Expansion of (1+x) / (1-2*x-6*x^2).

1, 3, 12, 42, 156, 564, 2064, 7512, 27408, 99888, 364224, 1327776, 4840896, 17648448, 64342272, 234575232, 855204096, 3117859584, 11366943744, 41441044992, 151083752448, 550813774848, 2008130064384, 7321142777856, 26691065942016, 97308988551168

Offset

0,2

Comments

Number of walks of length n in the graph K_{1,1,1,2} starting at vertex 0 when the edges are given by {{0,1}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}.

Also, by symmetry, the number of walks of length n starting at vertex 2 in the same graph.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Sean A. Irvine, Walks on Graphs.

Formula

a(n) = 3*A133592(n)/2 for n>0.

a(n) = 3*a(n-1)+4*a(n-2)-6*a(n-3); a(0)=1, a(1)=3, a(2)=12. - Vincenzo Librandi, Oct 13 2025

Example

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

Maple

a:= n-> (<<0|1|0|1|1>, <1|0|1|1|1>, <0|1|0|1|1>, <1|1|1|0|1>, <1|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-6*x^2), {x, 0, 32}], x]
LinearRecurrence[{3, 4, -6}, {1, 3, 12}, 33] (* Vincenzo Librandi, Oct 13 2025 *)

Prog

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

Crossrefs

Cf. A133592, A384712 (vertices 1, 3, 4).

Sequence in context: A067819 A094970 A065179 * A048121 A191112 A066987

Adjacent sequences: A384708 A384709 A384710 * A384712 A384713 A384714

Keyword

nonn,easy,walk

Author

Sean A. Irvine, Jun 07 2025

Status

approved