This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 |i-j|=1 or |i-j|=2. A trail can visit the same vertex more than once, but it cannot repeat an edge. LINKS 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; a = 1; a = 2; a = 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 22:57 EDT 2019. Contains 323597 sequences. (Running on oeis4.)