

A190277


Number of trails between opposite vertices in a triangle strip.


0



1, 1, 2, 4, 9, 23, 62, 174, 497, 1433, 4150, 12044, 34989, 101695, 295642, 859566, 2499277, 7267081, 21130538, 61441732, 178655937, 519483767, 1510520966, 4392195390, 12771343961, 37135696841
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n) is the number of trails from 1 to n in an undirected graph with vertex set {1, 2, ..., n}, where i and j are adjacent if and only if ij=1 or ij=2. A trail can visit the same vertex more than once, but it cannot repeat an edge.


LINKS

Table of n, a(n) for n=1..26.
StackExchange, Counting trails in a triangular grid
Index entries for linear recurrences with constant coefficients, signature (3, 1, 3, 2).


FORMULA

a(n) = 3*a(n1) + a(n2)  3*a(n3)  2*a(n4) for n > 4.
G.f.: x*(12*x2*x^2)/(13xx^2+3*x^3+2*x^4).


EXAMPLE

For n = 5 there are 9 trails: 12345, 1235, 12435, 1245, 132435, 13245, 134235, 1345, and 135.


MAPLE

a := [1, 1, 2, 4, seq(0, i = 1 .. 36)]: for n from 5 to 40 do a[n] := 3*a[n1]+a[n2]3*a[n3]2*a[n4] end do; a;


MATHEMATICA

a[1] = 1; a[2] = 1; a[3] = 2; a[4] = 4; a[n_] := a[n] = 3 a[n  1] + a[n  2]  3 a[n  3]  2 a[n  4]; Table[a[n], {n, 1, 40}]
LinearRecurrence[{3, 1, 3, 2}, {1, 1, 2, 4}, 30] (* Harvey P. Dale, May 24 2011 *)


CROSSREFS

Sequence in context: A213683 A032010 A032028 * A274882 A127384 A058585
Adjacent sequences: A190274 A190275 A190276 * A190278 A190279 A190280


KEYWORD

nonn,easy,walk


AUTHOR

David Radcliffe, May 07 2011


STATUS

approved



