cp's OEIS Frontend

A051736 Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.

%I A051736 #55 Jul 02 2025 16:01:58
%S A051736 1,5,17,63,227,827,2999,10897,39561,143677,521721,1894607,6879979,
%T A051736 24983923,90725999,329460929,1196397873,4344577397,15776816033,
%U A051736 57291635519,208047769363,755500774443,2743511349031,9962735709201,36178491743225,131377896967213,477083233044745
%N A051736 Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.
%C A051736 Also the number of independent vertex sets and vertex covers in the 3 X n grid graph. - _Eric W. Weisstein_, Sep 21 2017
%H A051736 Reinhard Zumkeller, <a href="/A051736/b051736.txt">Table of n, a(n) for n = 0..999</a>
%H A051736 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 A051736 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 A051736 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 A051736 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A051736 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H A051736 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H A051736 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,6,0,-1).
%F A051736 a(n) = 2*a(n-1) + 6*a(n-2) - a(n-4).
%F A051736 G.f.: (1+x)*(1+2*x-x^2)/(1-2*x-6*x^2+x^4). - _Philippe Deléham_, Sep 07 2006
%e A051736 There are five 3 X 1 (0,1)-matrices with no consecutive 1's:
%e A051736   0 0 0
%e A051736   0 0 1
%e A051736   0 1 0
%e A051736   1 0 0
%e A051736   1 0 1
%e A051736 There are 17 3 X 2 (0,1)-matrices with no consecutive 1's:
%e A051736 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 A051736 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 A051736 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 A051736 LinearRecurrence[{2, 6, 0, -1}, {1, 5, 17, 63}, 40] (* _Harvey P. Dale_, Mar 05 2013 *)
%t A051736 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 A051736 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 A051736 (Haskell)
%o A051736 a051736 n = a051736_list !! (n-1)
%o A051736 a051736_list = 1 : 5 : 17 : 63 : zipWith (-) (map (* 2) $ drop 2 $
%o A051736    zipWith (+) (map (* 3) a051736_list) (tail a051736_list)) a051736_list
%o A051736 -- _Reinhard Zumkeller_, Apr 02 2012
%o A051736 (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 A051736 Row 3 of A089934. Row sums of A371967.
%Y A051736 Cf. A051737.
%K A051736 easy,nonn,nice
%O A051736 0,2
%A A051736 _Stephen G Penrice_, Dec 06 1999
%E A051736 More terms from _James Sellers_, Dec 08 1999
%E A051736 More terms from _Michel Marcus_, Sep 17 2014
%E A051736 Offset fixed by _Eric W. Weisstein_, Sep 21 2017