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,2

Comments

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

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).

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

Example

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

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 *)

Prog

(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
(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

Crossrefs

Row 3 of A089934. Row sums of A371967.

Cf. A051737.

Sequence in context: A273704 A146444 A128073 * A301560 A099528 A149667

Adjacent sequences: A051733 A051734 A051735 * A051737 A051738 A051739

Keyword

easy,nonn,nice

Author

Stephen G Penrice, Dec 06 1999

Extensions

More terms from James A. Sellers, Dec 08 1999

More terms from Michel Marcus, Sep 17 2014

Offset fixed by Eric W. Weisstein, Sep 21 2017

Status

approved