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,2

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

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).

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

Example

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

Crossrefs

Column 3 of A197054.

Sequence in context: A240877 A218008 A303346 * A303438 A348396 A104723

Adjacent sequences: A197046 A197047 A197048 * A197050 A197051 A197052

Keyword

nonn,easy,changed

Author

R. H. Hardin, Oct 09 2011

Extensions

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

Status

approved