A190277 Number of trails between opposite vertices in a triangle strip.

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

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 |i-j|=1 or |i-j|=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(n-1) + a(n-2) - 3*a(n-3) - 2*a(n-4) for n > 4.

G.f.: x*(1-2*x-2*x^2)/(1-3x-x^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[n-1]+a[n-2]-3*a[n-3]-2*a[n-4] 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 A337721

Adjacent sequences: A190274 A190275 A190276 * A190278 A190279 A190280

Keyword

nonn,easy,walk

Author

David Radcliffe, May 07 2011

Status

approved