login
Number of trails between opposite vertices in a triangle strip.
0

%I #15 Aug 01 2015 09:29:35

%S 1,1,2,4,9,23,62,174,497,1433,4150,12044,34989,101695,295642,859566,

%T 2499277,7267081,21130538,61441732,178655937,519483767,1510520966,

%U 4392195390,12771343961,37135696841

%N Number of trails between opposite vertices in a triangle strip.

%C 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.

%H StackExchange, <a href="http://math.stackexchange.com/questions/37553">Counting trails in a triangular grid</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3, 1, -3, -2).

%F a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3) - 2*a(n-4) for n > 4.

%F G.f.: x*(1-2*x-2*x^2)/(1-3x-x^2+3*x^3+2*x^4).

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

%p 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;

%t 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}]

%t LinearRecurrence[{3,1,-3,-2},{1,1,2,4},30] (* _Harvey P. Dale_, May 24 2011 *)

%K nonn,easy,walk

%O 1,3

%A _David Radcliffe_, May 07 2011