Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #53 Aug 27 2024 05:29:39
%S 1,5,17,63,227,827,2999,10897,39561,143677,521721,1894607,6879979,
%T 24983923,90725999,329460929,1196397873,4344577397,15776816033,
%U 57291635519,208047769363,755500774443,2743511349031,9962735709201,36178491743225,131377896967213,477083233044745
%N Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.
%C Also the number of independent vertex sets and vertex covers in the 3 X n grid graph. - _Eric W. Weisstein_, Sep 21 2017
%H Reinhard Zumkeller, <a href="/A051736/b051736.txt">Table of n, a(n) for n = 0..999</a>
%H N. J. Calkin and H. S. Wilf, <a href="http://hdl.handle.net/1853/31277">The number of independent sets in a grid graph</a>, preprint, SIAM J. Discrete Math., 11(1), 54-60.
%H N. J. Calkin and H. S. Wilf, <a href="http://dx.doi.org/10.1137/S089548019528993X">The number of independent sets in a grid graph</a>, SIAM J. Discrete Math, 11 (1998) 54-60.
%H Reinhardt Euler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Euler/euler1.html">The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
%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/IndependentVertexSet.html">Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,6,0,-1).
%F a(n) = 2*a(n-1) + 6*a(n-2) - a(n-4).
%F G.f.: (1+x)*(1+2*x-x^2)/(1-2*x-6*x^2+x^4). - _Philippe Deléham_, Sep 07 2006
%e There are five 3 X 1 (0,1)-matrices with no consecutive 1's:
%e 0 0 0
%e 0 0 1
%e 0 1 0
%e 1 0 0
%e 1 0 1
%e There are 17 3 X 2 (0,1)-matrices with no consecutive 1's:
%e 0 0, 0 1, 0 0, 0 0, 0 1, 1 0, 1 0, 1 0, 0 0, 0 1, 0 0, 0 1, 0 0, 0 1, 0 0, 1 0, 1 0
%e 0 0, 0 0, 0 1, 0 0, 0 0, 0 0, 0 1, 0 0, 1 0, 1 0, 1 0, 1 0, 0 0, 0 0, 0 1, 0 0, 0 1
%e 0 0, 0 0, 0 0, 0 1, 0 1, 0 0, 0 0, 0 1, 0 0, 0 0, 0 1, 0 1, 1 0, 1 0, 1 0, 1 0, 1 0
%t LinearRecurrence[{2, 6, 0, -1}, {1, 5, 17, 63}, 40] (* _Harvey P. Dale_, Mar 05 2013 *)
%t CoefficientList[Series[(1 + 3 x + x^2 - x^3)/(1 - 2 x - 6 x^2 + x^4), {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 21 2017 *)
%t Table[-RootSum[1 - 6 #1^2 - 2 #1^3 + #1^4 &, 263 #1^n - 657 #1^(n + 1) - 331 #1^(n + 2) + 81 #1^(n + 3) &]/1994, {n, 0, 20}] (* _Eric W. Weisstein_, Sep 21 2017 *)
%o (Haskell)
%o a051736 n = a051736_list !! (n-1)
%o a051736_list = 1 : 5 : 17 : 63 : zipWith (-) (map (* 2) $ drop 2 $
%o zipWith (+) (map (* 3) a051736_list) (tail a051736_list)) a051736_list
%o -- _Reinhard Zumkeller_, Apr 02 2012
%o (PARI) Vec((1+3*x+x^2-x^3)/(1-2*x-6*x^2+x^4)+O(x^50)) \\ _Michel Marcus_, Sep 17 2014
%Y Row 3 of A089934. Row sums of A371967.
%Y Cf. A051737.
%K easy,nonn,nice
%O 0,2
%A _Stephen G Penrice_, Dec 06 1999
%E More terms from _James A. Sellers_, Dec 08 1999
%E More terms from _Michel Marcus_, Sep 17 2014
%E Offset fixed by _Eric W. Weisstein_, Sep 21 2017