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

1, 16, 108, 531, 2119, 7338, 23330, 70369, 204461, 576824, 1589880, 4304373, 11495305, 30376964, 79611466, 207289163, 536963245, 1385313538, 3562495802, 9138021569, 23392128783, 59784414592, 152598577140, 389109027023, 991382100235, 2524246846050, 6423930260330, 16341562302987

Offset

1,2

Links

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

Index entries for linear recurrences with constant coefficients, signature (13,-74,243,-506,668,-444,-217,903,-1018,416,384,-712,418,57,-262,160,7,-60,27,4,-8,1,1).

Formula

G.f.: x*(1 + 3*x - 26*x^2 + 68*x^3 - 174*x^4 + 269*x^5 + 113*x^6 - 963*x^7 + 977*x^8 + 253*x^9 - 778*x^10 + 466*x^11 - 275*x^12 - 263*x^13 + 307*x^14 - 176*x^15 - 15*x^16 + 171*x^17 - 63*x^18 - 59*x^19 + 4*x^20 - 3*x^21 + x^22 + 2*x^23)/((1 - x)^4*(1 - x - x^2)*(1 - 2*x - x^4)*(1 - 2*x + x^2 - x^3 - x^4)^2*(1 - 2*x - x^2 - 2*x^4 - x^5)). - Andrew Howroyd, Dec 22 2025

Example

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

Crossrefs

Row 4 of A391822.

Sequence in context: A224411 A260357 A056001 * A269188 A165558 A384014

Adjacent sequences: A163722 A163723 A163724 * A163726 A163727 A163728

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Extensions

a(18) onward from Andrew Howroyd, Dec 22 2025

Status

approved