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

1, 5, 17, 63, 227, 827, 2999, 10897, 39561, 143677, 521721, 1894607, 6879979, 24983923, 90725999, 329460929, 1196397873, 4344577397, 15776816033, 57291635519, 208047769363, 755500774443, 2743511349031, 9962735709201, 36178491743225, 131377896967213, 477083233044745

Offset: 0

Author

Stephen G Penrice, Dec 06 1999

Keywords

• easy
• nonn
• nice

Comments

Also the number of independent vertex sets and vertex covers in the 3 X n grid graph. - Eric W. Weisstein, Sep 21 2017

Examples

			There are five 3 X 1 (0,1)-matrices with no consecutive 1's:
  0 0 0
  0 0 1
  0 1 0
  1 0 0
  1 0 1
There are 17 3 X 2 (0,1)-matrices with no consecutive 1's:
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
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
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
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..999
• N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint, SIAM J. Discrete Math., 11(1), 54-60.
• N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math, 11 (1998) 54-60.
• Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Vertex Cover
• Index entries for linear recurrences with constant coefficients, signature (2,6,0,-1).

Crossrefs

Row 3 of A089934. Row sums of A371967.

Cf. A051737.

Programs

Haskell

a051736 n = a051736_list !! (n-1)
a051736_list = 1 : 5 : 17 : 63 : zipWith (-) (map (* 2) $ drop 2 $
   zipWith (+) (map (* 3) a051736_list) (tail a051736_list)) a051736_list
-- Reinhard Zumkeller, Apr 02 2012

Mathematica

LinearRecurrence[{2, 6, 0, -1}, {1, 5, 17, 63}, 40] (* Harvey P. Dale, Mar 05 2013 *)
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 *)
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 *)

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

Formula

a(n) = 2*a(n-1) + 6*a(n-2) - a(n-4).

G.f.: (1+x)*(1+2*x-x^2)/(1-2*x-6*x^2+x^4). - Philippe Deléham, Sep 07 2006

Extensions

More terms from James Sellers, Dec 08 1999

More terms from Michel Marcus, Sep 17 2014

Offset fixed by Eric W. Weisstein, Sep 21 2017