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

%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