A163723 Number of n X 2 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, 7, 21, 49, 101, 193, 351, 617, 1059, 1787, 2979, 4923, 8085, 13219, 21545, 35037, 56889, 92269, 149539, 242229, 392231, 634967, 1027751, 1663319, 2691721, 4355743, 7048221, 11404777, 18453869, 29859577, 48314439, 78175073, 126490635, 204666899, 331158795, 535827027

Offset

1,2

Links

R. H. Hardin, Table of n, a(n) for n=1..100

Index entries for linear recurrences with constant coefficients, signature (4,-5,1,2,-1).

Formula

Empirical: a(n) = 4*a(n-1) - 5*a(n-2) + a(n-3) + 2*a(n-4) - a(n-5).

From R. J. Mathar, Aug 11 2009: (Start)

Empirical: a(n) = A006355(n+7) - n^2 - 7*n - 17.

Empirical g.f.: x*(1+3*x-2*x^2+x^4-x^3)/((x^2+x-1)*(x-1)^3). (End)

Formulas confirmed using the transfer matrix method. - Andrew Howroyd, Dec 24 2025

Example

All solutions for n=3
...1.1...1.1...1.1...1.1...1.1...0.0...0.0...0.0...0.0...1.0...0.0...0.0...0.1
...0.0...0.1...1.0...1.1...1.0...0.0...0.1...1.0...1.1...1.0...1.1...1.1...1.1
...0.0...0.0...0.0...0.0...1.0...1.1...1.1...1.1...1.1...1.1...0.0...0.1...0.0
------
...0.0...0.1...1.0...1.0...1.1...1.1...0.1...1.1
...1.1...1.1...1.1...1.1...0.1...1.0...0.1...0.1
...1.0...1.0...0.0...0.1...0.1...1.1...1.1...1.1

Crossrefs

Row 2 of A391822.

Cf. A006355.

Sequence in context: A195965 A137182 A011927 * A146669 A146637 A146701

Adjacent sequences: A163720 A163721 A163722 * A163724 A163725 A163726

Keyword

nonn,easy

Author

R. H. Hardin, Aug 03 2009

Status

approved