A197049 Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

1, 2, 4, 10, 18, 38, 78, 156, 320, 654, 1326, 2706, 5518, 11228, 22884, 46634, 94978, 193518, 394286, 803220, 1636448, 3334030, 6792334, 13838202, 28192958, 57437684, 117018884, 238404906, 485705682, 989536598, 2016000430, 4107230284, 8367729920, 17047719214

Offset: 0

Author

R. H. Hardin, Oct 09 2011

Keywords

• nonn
• easy

Comments

Every 0 is next to 0 0's, every 1 is next to 1 0's, every 2 is next to 2 0's, every 3 is next to 3 0's, every 4 is next to 4 0's.

In other words, the number of maximal independent vertex sets (and minimal vertex covers) in the 3 X n grid graph. - Eric W. Weisstein, Aug 07 2017

Examples

			Some solutions for n=5:
  2  0  2    0  1  1    2  0  1    0  3  0    0  3  0    0  3  0    0  2  0
  0  4  0    1  2  0    0  2  1    3  0  2    2  0  2    2  0  3    1  1  1
  2  0  3    2  0  3    2  1  0    0  2  1    1  1  1    1  2  0    1  0  2
  1  2  0    0  4  0    0  2  1    1  2  0    0  3  0    0  2  1    1  2  0
  0  1  1    2  0  2    2  0  1    1  0  2    2  0  2    2  0  1    0  1  1
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n = 1..200 from R. H. Hardin)
• George Spahn, Counting Maximal Seat Assignments that Obey Social Distancing, Talk at Rutgers Experimental Mathematics Seminar, Feb. 1, 2024. Addresses this sequence on slides 26-32, but under incorrect A-number A157049.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover
• Index entries for linear recurrences with constant coefficients, signature (1,1,3,-1,-1).

Crossrefs

Column 3 of A197054.

Formula

Empirical: a(n) = a(n-1) +a(n-2) +3*a(n-3) -a(n-4) -a(n-5) for n>6.

Equivalent g.f.: -(2*x^6-x^5+x^4-x^3-x^2-x-1)/(x^5+x^4-3*x^3-x^2-x+1). - R. J. Mathar, Oct 10 2011

Spahn (see link) provides a proof of the generating function. - Hugo Pfoertner, Apr 18 2024

Extensions

a(0)=1 prepended by Alois P. Heinz, Apr 18 2024