login
A197049
Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.
5
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
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
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Oct 09 2011
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Apr 18 2024
STATUS
approved