login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051736 Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column. 8
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 (list; graph; refs; listen; history; text; internal format)
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

H. Wilf, The number of independent sets in a grid graph (With N. Calkin) [Broken link]

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+3*x+x^2-x^3)/(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.

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 (spenrice(AT)ets.org), 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 21:47 EST 2018. Contains 317275 sequences. (Running on oeis4.)