cp's OEIS Frontend

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

%I A197049 #29 Feb 16 2025 08:33:15
%S A197049 1,2,4,10,18,38,78,156,320,654,1326,2706,5518,11228,22884,46634,94978,
%T A197049 193518,394286,803220,1636448,3334030,6792334,13838202,28192958,
%U A197049 57437684,117018884,238404906,485705682,989536598,2016000430,4107230284,8367729920,17047719214
%N A197049 Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.
%C A197049 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.
%C A197049 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
%H A197049 Alois P. Heinz, <a href="/A197049/b197049.txt">Table of n, a(n) for n = 0..2000</a> (terms n = 1..200 from R. H. Hardin)
%H A197049 George Spahn, <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/spahn2024.pdf">Counting Maximal Seat Assignments that Obey Social Distancing</a>, Talk at Rutgers Experimental Mathematics Seminar, Feb. 1, 2024. Addresses this sequence on slides 26-32, but under incorrect A-number A157049.
%H A197049 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A197049 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%H A197049 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>
%H A197049 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,3,-1,-1).
%F A197049 Empirical: a(n) = a(n-1) +a(n-2) +3*a(n-3) -a(n-4) -a(n-5) for n>6.
%F A197049 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
%F A197049 Spahn (see link) provides a proof of the generating function. - _Hugo Pfoertner_, Apr 18 2024
%e A197049 Some solutions for n=5:
%e A197049   2  0  2    0  1  1    2  0  1    0  3  0    0  3  0    0  3  0    0  2  0
%e A197049   0  4  0    1  2  0    0  2  1    3  0  2    2  0  2    2  0  3    1  1  1
%e A197049   2  0  3    2  0  3    2  1  0    0  2  1    1  1  1    1  2  0    1  0  2
%e A197049   1  2  0    0  4  0    0  2  1    1  2  0    0  3  0    0  2  1    1  2  0
%e A197049   0  1  1    2  0  2    2  0  1    1  0  2    2  0  2    2  0  1    0  1  1
%Y A197049 Column 3 of A197054.
%K A197049 nonn,easy
%O A197049 0,2
%A A197049 _R. H. Hardin_, Oct 09 2011
%E A197049 a(0)=1 prepended by _Alois P. Heinz_, Apr 18 2024