A059524 Number of nonzero 4 X n binary arrays with all 1's connected.

0, 10, 108, 1126, 11506, 116166, 1168586, 11749134, 118127408, 1187692422, 11941503498, 120064335342, 1207171430452, 12137349489598, 122033415224922, 1226969238084836, 12336404001299200, 124034783402890620, 1247091736942594618, 12538723071673581562

Offset: 0

Author

David Radcliffe, Jan 21 2001

Keywords

• nonn

Comments

Old name was "Number of 4 X n checkerboards in which the set of red squares is edge connected".

The number of connected (non-null) induced subgraphs in the grid graph P_4 X P_n. - Andrew Howroyd, May 20 2017

Examples

			a(1) = 10 because there are 4 positions to place a single 1, 3 ways to place a pair of adjacent 1's, 2 ways to place a triple of connected 1's, and 1 way for the all-1's array: 4+3+2+1=10. - _R. J. Mathar_, Mar 13 2023
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Index entries for linear recurrences with constant coefficients, signature (17,-90,230,-272,-75,623,-632,65,255,-198,162,-96,11,1).

Crossrefs

Row 4 of A287151.

Cf. A059020, A059021.

Formula

Empirical g.f.: 2*x*(1 + x)*(5 - 36*x + 131*x^2 - 239*x^3 + 131*x^4 + 94*x^5 - 157*x^6 + 61*x^7 - 73*x^8 + 18*x^9 + x^10) / ((1 - x)^2*(1 - 15*x + 59*x^2 - 97*x^3 + 19*x^4 + 210*x^5 - 222*x^6 - 22*x^7 + 113*x^8 - 7*x^9 + 71*x^10 - 13*x^11 - x^12)). - Colin Barker, Oct 11 2017

The recurrence is correct. See A287151. - Andrew Howroyd, Dec 18 2024

Extensions

Clearer name from R. H. Hardin, Jul 06 2009

a(16) corrected by Andrew Howroyd, May 20 2017