A163687 Number of n X 4 binary arrays with all 1s connected, a path of 1s from upper left corner to lower right corner, and no 1 having more than two 1s adjacent.

1, 8, 39, 132, 389, 1095, 3107, 8790, 24449, 66724, 179212, 475169, 1247181, 3249223, 8420475, 21735923, 55926076, 143501956, 367381497, 938864371, 2396062211, 6108616160, 15560958273, 39614145740, 100795424446, 256362601215, 651824860468, 1656917910983, 4211037564601, 10700734731455

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-200, 180,24,-328,471, -260,-168,440,-320, -12,234,-172,14, 86,-45,4,24, -2,1,4,1).

Formula

G.f.: x*(1 - 2*x + 4*x^2 - 18*x^3 + 64*x^4 - 115*x^5 + 158*x^6 - 169*x^7 + 221*x^8 + 40*x^9 - 484*x^10 + 673*x^11 - 204*x^12 - 323*x^13 + 451*x^14 - 438*x^15 + 22*x^16 + 297*x^17 - 366*x^18 - 74*x^19 + 58*x^20 - 166*x^21 - 79*x^22 - 4*x^23 - 12*x^24 - x^25 + 2*x^26)/((1 - x + x^3)^2*(1 - 2*x + x^2 - x^3 - x^4)^2*(1 - 2*x + 3*x^2 + x^5)*(1 - 2*x - x^2 - 2*x^4 - x^5)). - Andrew Howroyd, Dec 21 2025

Example

All solutions for n=2
...1.0.0.0...1.0.0.1...1.1.0.0...1.1.0.1...1.1.1.0...1.1.1.0...1.1.1.1
...1.1.1.1...1.1.1.1...0.1.1.1...0.1.1.1...0.0.1.1...1.0.1.1...0.0.0.1
------
...1.1.1.1
...1.0.0.1

Crossrefs

Row 4 of A391818.

Sequence in context: A245135 A200157 A101374 * A060446 A318267 A063002

Adjacent sequences: A163684 A163685 A163686 * A163688 A163689 A163690

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Extensions

a(24) onward from Andrew Howroyd, Dec 21 2025

Status

approved