A163685 Number of nX2 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, 3, 5, 8, 13, 20, 32, 52, 85, 138, 223, 360, 582, 942, 1525, 2468, 3993, 6460, 10452, 16912, 27365, 44278, 71643, 115920, 187562, 303482, 491045, 794528, 1285573, 2080100, 3365672, 5445772, 8811445, 14257218, 23068663, 37325880, 60394542

Offset

1,2

Links

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

Formula

Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-4) for n>=7

Empirical: G.f.: x*(-x^3-x^4+x^5-x-1)/((x^2-x+1)*(x^2+x-1)). a(n)=5*A000045(n)/2-A010892(n+1)/2, n>2. [From R. J. Mathar, Aug 11 2009]

Example

All solutions for n=5
...1.0...1.0...1.1...1.1...1.0...1.1...1.0...1.1...1.0...1.0...1.1...1.1...1.1
...1.0...1.0...1.0...1.0...1.0...1.0...1.0...1.0...1.1...1.1...0.1...0.1...0.1
...1.1...1.1...1.1...1.1...1.0...1.0...1.0...1.0...0.1...0.1...0.1...0.1...1.1
...0.1...0.1...0.1...0.1...1.0...1.0...1.1...1.1...0.1...0.1...0.1...0.1...1.0
...0.1...1.1...0.1...1.1...1.1...1.1...0.1...0.1...0.1...1.1...0.1...1.1...1.1

Crossrefs

Sequence in context: A265067 A265068 A227547 * A080614 A079122 A265069

Adjacent sequences: A163682 A163683 A163684 * A163686 A163687 A163688

Keyword

nonn

Author

R. H. Hardin Aug 03 2009

Status

approved