A183777 Half the number of (n+1) X 5 binary arrays with no 2 X 2 subblock having exactly 2 ones.

16, 85, 567, 3435, 21935, 136843, 864671, 5431499, 34228999, 215374371, 1356329167, 8537916907, 53757639287, 338436138739, 2130795330527, 13415038654331, 84459841870343, 531746080445251, 3347809160159215, 21077341291331531, 132700223506346903, 835462783565678867, 5259963941120795903

Offset

0,1

Links

R. H. Hardin, Table of n, a(n) for n = 0..200

Robert Israel, Maple-assisted proof of empirical formula

Index entries for linear recurrences with constant coefficients, signature (5,26,-98,-188,580,392,-1024,-256,512).

Formula

Empirical: a(n) = 5*a(n-1) + 26*a(n-2) - 98*a(n-3) - 188*a(n-4) + 580*a(n-5) + 392*a(n-6) - 1024*a(n-7) - 256*a(n-8) + 512*a(n-9).

Empirical g.f.: x*(85 + 142*x - 1610*x^2 - 1652*x^3 + 9404*x^4 + 4072*x^5 - 16544*x^6 - 3072*x^7 + 8192*x^8) / (1 - 5*x - 26*x^2 + 98*x^3 + 188*x^4 - 580*x^5 - 392*x^6 + 1024*x^7 + 256*x^8 - 512*x^9). - Colin Barker, Apr 04 2018

Empirical formula verified by Robert Israel, Jul 01 2018: see link.

Example

Some solutions with a(1,1)=0 for 3 X 5:
  0 1 0 0 0     0 1 0 0 1     0 1 1 1 0     0 0 0 0 0
  1 1 1 0 0     0 0 0 0 0     1 1 1 1 1     0 0 1 0 0
  1 1 0 0 0     0 0 0 1 0     0 1 0 1 0     0 1 1 1 0

Crossrefs

Column k=4 of A183782.

Sequence in context: A118675 A223962 A252834 * A050256 A223835 A224143

Adjacent sequences: A183774 A183775 A183776 * A183778 A183779 A183780

Keyword

nonn,easy

Author

R. H. Hardin, Jan 07 2011

Extensions

a(0) prepended by Andrew Howroyd, Jan 09 2025

Status

approved