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
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).
Programs
-
Mathematica
LinearRecurrence[{4, 9, -5, -4, 1}, {1, 8, 41, 227, 1234}, 24] (* Jean-François Alcover, Nov 05 2017 *) -
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
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).
Extensions
More terms from James Sellers, Dec 08 1999
More terms from Michel Marcus, Sep 17 2014