A089936 Number of 5 X n matrices with entries {0,1} without adjacent 0's in any row or column. 5th row of A089934.

13, 99, 827, 6743, 55447, 454385, 3729091, 30584687, 250916131, 2058249165, 16884649135, 138508056265, 1136221529549, 9320704799431, 76460212316453, 627222736888811, 5145271430670385, 42207992410219447, 346243111960194009

Offset: 1

Author

Marc LeBrun, Nov 15 2003

Keywords

• nonn

Comments

Row/columns 1 through 7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.

Number of independent vertex sets in the grid graph P_5 X P_n. - Andrew Howroyd, Jun 06 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• 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.

Crossrefs

Row 5 of A089934.

Cf. A000045, A001333, A051736, A051737, A089935, A089937, A089938.

Formula

G.f.: x*(13 + 47*x - 37*x^2 - 129*x^3 + 68*x^4 + 49*x^5 - 23*x^6 - 3*x^7 + x^8) / (1 - 4*x - 36*x^2 + 105*x^4 - 15*x^5 - 64*x^6 + 20*x^7 + 4*x^8 - x^9) (conjectured). - Colin Barker, Jun 06 2017

The above conjecture is correct since the order of the recurrence is A089935(5) = 9. - Andrew Howroyd, Dec 24 2019