|
%I #28 Apr 18 2024 08:14:03
%S 1,2,4,10,18,38,78,156,320,654,1326,2706,5518,11228,22884,46634,94978,
%T 193518,394286,803220,1636448,3334030,6792334,13838202,28192958,
%U 57437684,117018884,238404906,485705682,989536598,2016000430,4107230284,8367729920,17047719214
%N Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.
%C 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,3,-1,-1).
%F Empirical: a(n) = a(n-1) +a(n-2) +3*a(n-3) -a(n-4) -a(n-5) for n>6.
%F 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 Spahn (see link) provides a proof of the generating function. - _Hugo Pfoertner_, Apr 18 2024
%e Some solutions for n=5:
%e 2 0 2 0 1 1 2 0 1 0 3 0 0 3 0 0 3 0 0 2 0
%e 0 4 0 1 2 0 0 2 1 3 0 2 2 0 2 2 0 3 1 1 1
%e 2 0 3 2 0 3 2 1 0 0 2 1 1 1 1 1 2 0 1 0 2
%e 1 2 0 0 4 0 0 2 1 1 2 0 0 3 0 0 2 1 1 2 0
%e 0 1 1 2 0 2 2 0 1 1 0 2 2 0 2 2 0 1 0 1 1
%Y Column 3 of A197054.
%K nonn,easy,changed
%O 0,2
%A _R. H. Hardin_, Oct 09 2011
%E a(0)=1 prepended by _Alois P. Heinz_, Apr 18 2024
| 