A221678 Number of 0..3 arrays of length n with each element differing from at least one neighbor by 1 or less, starting with 0.

0, 2, 5, 20, 68, 241, 844, 2966, 10413, 36568, 128408, 450913, 1583400, 5560186, 19524853, 68562444, 240760252, 845440977, 2968805844, 10425101678, 36608235997, 128551546480, 451414815600, 1585164405441, 5566379537040

Offset

1,2

Comments

Column 3 of A221683.

Links

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

Formula

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

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

Example

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

Crossrefs

Sequence in context: A274239 A271858 A189734 * A297350 A027041 A355866

Adjacent sequences: A221675 A221676 A221677 * A221679 A221680 A221681

Keyword

nonn

Author

R. H. Hardin, Jan 22 2013

Status

approved