A163716 Number of n X 4 binary arrays with all 1s connected, a path of 1s from top row to bottom row, and no 1 having more than two 1s adjacent.

10, 49, 163, 531, 1611, 4601, 12865, 35525, 96583, 258479, 683455, 1791811, 4667275, 12093461, 31202401, 80234775, 205773699, 526638873, 1345615355, 3433715529, 8753124861, 22295263671, 56752887761, 144393774321, 367232290953, 933688335909, 2373343399139, 6031696212545

Offset

1,1

Links

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

Index entries for linear recurrences with constant coefficients, signature (6,-13,14,-7,-9,16,-8,2,11,1,3,4,1).

Formula

G.f.: x*(10 - 11*x - x^2 + 50*x^3 - 72*x^4 - 11*x^5 + 190*x^6 + 74*x^7 + 84*x^8 + 2*x^9 - 129*x^10 - 56*x^11 - 21*x^12 - 45*x^13 - 22*x^14 - 2*x^15)/((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.0.0.0...1.0.0.0...1.1.0.0...1.1.0.0...1.1.1.0...0.0.1.0...0.0.1.0
...1.0.0.0...1.1.0.0...1.0.0.0...1.1.0.0...1.0.0.0...0.0.1.0...0.0.1.1
------
...0.0.1.0...0.0.1.1...0.0.1.1...0.0.1.1...0.1.1.0...0.1.1.0...0.1.1.0
...0.1.1.0...0.0.1.0...0.0.1.1...0.1.1.0...0.0.1.0...0.0.1.1...0.1.1.0
------
...1.1.1.0...1.1.1.0...0.1.0.0...0.1.0.0...0.1.0.0...0.1.1.0...0.1.1.0
...0.0.1.0...0.0.1.1...0.1.0.0...0.1.1.0...1.1.0.0...0.1.0.0...1.1.0.0
------
...1.1.0.0...1.1.0.0...0.1.1.1...0.1.1.1...0.0.0.1...0.0.0.1...0.0.1.1
...0.1.0.0...0.1.1.0...0.1.0.0...1.1.0.0...0.0.0.1...0.0.1.1...0.0.0.1
------
...0.1.1.1...1.0.0.0...1.1.1.0...1.1.1.1...0.0.1.0...0.0.1.1...0.1.1.1
...0.0.0.1...1.1.1.0...1.0.1.0...1.0.0.0...1.1.1.0...1.1.1.0...0.1.0.1
------
...1.1.1.1...0.1.1.1...1.1.1.0...1.1.1.1...0.1.0.0...1.1.0.0...0.0.0.1
...0.0.0.1...1.1.0.1...1.0.1.1...1.0.0.1...0.1.1.1...0.1.1.1...0.1.1.1
------
...1.0.0.0...1.0.1.0...1.0.1.1...0.1.0.1...1.1.0.1...0.0.0.1...1.0.0.1
...1.1.1.1...1.1.1.0...1.1.1.0...0.1.1.1...0.1.1.1...1.1.1.1...1.1.1.1

Crossrefs

Column 4 of A391822.

Sequence in context: A370216 A307904 A226797 * A271662 A244864 A051947

Adjacent sequences: A163713 A163714 A163715 * A163717 A163718 A163719

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Extensions

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

Status

approved