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

17, 37, 77, 163, 343, 723, 1523, 3209, 6761, 14245, 30013, 63235, 133231, 280707, 591427, 1246089, 2625409, 5531525, 11654477, 24555043, 51735495, 109002515, 229659507, 483874057, 1019483609, 2147969733, 4525598973, 9535072003

Offset

1,1

Comments

Column 2 of A200871.

Links

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

Formula

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

Empirical g.f.: x*(17 + 3*x + 3*x^2 + 9*x^3) / (1 - 2*x - x^4). - Colin Barker, Oct 15 2017

Example

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

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, 3}]; a[n_] := Sum[a[n, x, y], {x, 3}, {y, 3}]; Array[a, 25] (* Giovanni Resta, Mar 05 2014 *)

Crossrefs

Sequence in context: A050952 A256517 A323603 * A319245 A093930 A048880

Adjacent sequences: A200862 A200863 A200864 * A200866 A200867 A200868

Keyword

nonn

Author

R. H. Hardin, Nov 23 2011

Status

approved