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

1, 8, 41, 227, 1234, 6743, 36787, 200798, 1095851, 5980913, 32641916, 178150221, 972290957, 5306478436, 28961194501, 158061670175, 862654025422, 4708111537971, 25695485730239, 140238391149386, 765379824048327, 4177217595760125, 22798023012345528, 124424893212114297

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint.

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.

Y. Kong, General recurrence theory of ligand binding on a three-dimensional lattice, J. Chem. Phys. Vol. 111 (1999), pp. 4790-4799 (set omega = 1 in Eq. (48)).

Index entries for linear recurrences with constant coefficients, signature (4,9,-5,-4,1).

Formula

From Yong Kong (ykong(AT)curagen.com), Dec 24 2000: (Start)

a(n) = 4*a(n - 1) + 9*a(n - 2) - 5*a(n - 3) - 4*a(n - 4) + a(n - 5);

G.f.: (1 + 4*x - 4*x^3 + x^4)/(1 - 4*x - 9*x^2 + 5*x^3 + 4*x^4 - x^5). (End)

a(n) = 2*a(n - 1) + 18*a(n - 2) + 9*a(n - 3) - 23*a(n - 4) - 2*a(n - 5) + 6*a(n - 6) - a(n - 7).

Mathematica

LinearRecurrence[{4, 9, -5, -4, 1}, {1, 8, 41, 227, 1234}, 24] (* Jean-François Alcover, Nov 05 2017 *)

Prog

(PARI) Vec((1+4*x-4*x^3+x^4)/(1-4*x-9*x^2+5*x^3+4*x^4-x^5) + O(x^50)) \\ Michel Marcus, Sep 17 2014

Crossrefs

Row 4 of A089934.

Cf. A051736.

Sequence in context: A037577 A265149 A209822 * A209841 A196927 A188209

Adjacent sequences: A051734 A051735 A051736 * A051738 A051739 A051740

Keyword

easy,nonn

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

Status

approved