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
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Oct 09 2011
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Apr 18 2024
STATUS
approved