|
%I #33 Sep 13 2023 11:16:50
%S 1,8,41,227,1234,6743,36787,200798,1095851,5980913,32641916,178150221,
%T 972290957,5306478436,28961194501,158061670175,862654025422,
%U 4708111537971,25695485730239,140238391149386,765379824048327,4177217595760125,22798023012345528,124424893212114297
%N Number of 4 X n (0,1)-matrices with no consecutive 1's in any row or column.
%H Colin Barker, <a href="/A051737/b051737.txt">Table of n, a(n) for n = 0..1000</a>
%H N. J. Calkin and H. S. Wilf, <a href="http://hdl.handle.net/1853/31277">The number of independent sets in a grid graph</a>, preprint.
%H N. J. Calkin and H. S. Wilf, <a href="http://dx.doi.org/10.1137/S089548019528993X">The number of independent sets in a grid graph</a>, SIAM J. Discrete Math, 11 (1998) 54-60.
%H Reinhardt Euler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Euler/euler1.html">The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
%H Y. Kong, <a href="http://dx.doi.org/10.1063/1.479242">General recurrence theory of ligand binding on a three-dimensional lattice</a>, J. Chem. Phys. Vol. 111 (1999), pp. 4790-4799 (set omega = 1 in Eq. (48)).
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,9,-5,-4,1).
%F From Yong Kong (ykong(AT)curagen.com), Dec 24 2000: (Start)
%F a(n) = 4*a(n - 1) + 9*a(n - 2) - 5*a(n - 3) - 4*a(n - 4) + a(n - 5);
%F 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)
%F 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).
%t LinearRecurrence[{4, 9, -5, -4, 1}, {1, 8, 41, 227, 1234}, 24] (* _Jean-François Alcover_, Nov 05 2017 *)
%o (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
%Y Row 4 of A089934.
%Y Cf. A051736.
%K easy,nonn
%O 0,2
%A _Stephen G Penrice_, Dec 06 1999
%E More terms from _James A. Sellers_, Dec 08 1999
%E More terms from _Michel Marcus_, Sep 17 2014
|
