A200866 Number of 0..3 arrays x(0..n+1) of n+2 elements without any interior element greater than both neighbors or less than both neighbors.

36, 94, 236, 602, 1528, 3882, 9858, 25038, 63592, 161514, 410218, 1041884, 2646208, 6720920, 17069998, 43354902, 110114102, 279671154, 710317326, 1804085608, 4582071648, 11637685314, 29557748082, 75071670020, 190669317026, 484267746348, 1229957991200, 3123884816870

Offset

1,1

Links

R. H. Hardin, Table of n, a(n) for n = 1..210

Formula

Empirical: a(n) = 2*a(n-1) +a(n-2) +2*a(n-4) +a(n-5).

Empirical g.f.: 2*x*(18 + 11*x + 6*x^2 + 18*x^3 + 8*x^4) / (1 - 2*x - x^2 - 2*x^4 - x^5). - Colin Barker, Oct 15 2017

Example

Some solutions for n=3:
..1....0....1....3....0....1....1....2....0....0....3....0....0....0....0....3
..2....1....3....1....2....0....1....2....3....1....2....2....0....0....0....2
..2....2....3....1....3....0....0....2....3....3....2....3....0....2....2....0
..1....2....3....2....3....2....0....2....3....3....1....3....1....2....3....0
..0....3....0....3....3....2....3....1....2....1....1....2....2....0....3....3

Mathematica

a[0, x_, y_] := 1; a[n_, x_, y_] := a[n, x, y] = Sum[If[z <=x<= y || y <=x<= z, a[n-1, z, x], 0], {z, 4}]; a[n_] := Sum[a[n, x, y], {x, 4}, {y, 4}]; Array[a, 25] (* Giovanni Resta, Mar 05 2014 *)

Crossrefs

Column 3 of A200871.

Sequence in context: A060936 A247246 A242238 * A324297 A250785 A057392

Adjacent sequences: A200863 A200864 A200865 * A200867 A200868 A200869

Keyword

nonn

Author

R. H. Hardin, Nov 23 2011

Status

approved