A268458 Number of length-4 0..n arrays with no adjacent pair x,x+1 followed at any distance by x+1,x.

11, 67, 229, 581, 1231, 2311, 3977, 6409, 9811, 14411, 20461, 28237, 38039, 50191, 65041, 82961, 104347, 129619, 159221, 193621, 233311, 278807, 330649, 389401, 455651, 530011, 613117, 705629, 808231, 921631, 1046561, 1183777, 1334059

Offset

1,1

Links

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

Formula

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

Empirical g.f.: x*(11 + 12*x + 4*x^2 - 4*x^3 + x^4) / (1 - x)^5. - Colin Barker, Jan 13 2019

Proof of empirical formula: There are (n+1)^4 arrays without the constraint. n of them are of the form (x,x+1,x+1,x) with 0 <= x <= n-1, n*(n+1) are of the form (x,x+1,x,y) with 0 <= x<= n-1 and 0<=y<=n, and n*(n+1) are of the form (y,x,x+1,x). That leaves n^4 + 4*n^3 + 4*n^2 + n + 1. - Robert Israel, Nov 28 2019

Example

Some solutions for n=9:
  2  7  0  3  8  5  3  3  4  5  8  9  9  8  2  4
  7  1  3  8  4  1  1  0  8  6  2  5  1  9  2  5
  6  0  7  3  1  1  0  5  8  2  0  8  1  4  0  2
  2  3  1  4  5  0  9  4  9  2  9  4  8  6  2  9

Maple

seq(n^4 + 4*n^3 + 4*n^2 + n + 1, n=1..100); # Robert Israel, Nov 28 2019

Crossrefs

Row 4 of A268457.

Sequence in context: A141969 A142645 A201605 * A001808 A258479 A035041

Adjacent sequences: A268455 A268456 A268457 * A268459 A268460 A268461

Keyword

nonn

Author

R. H. Hardin, Feb 04 2016

Status

approved