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

1, 5, 11, 21, 38, 66, 112, 187, 309, 507, 828, 1348, 2190, 3553, 5759, 9329, 15106, 24454, 39580, 64055, 103657, 167735, 271416, 439176, 710618, 1149821, 1860467, 3010317, 4870814, 7881162, 12752008, 20633203, 33385245, 54018483, 87403764

Offset

1,2

Links

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

Formula

Empirical: a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n >= 6.

Conjectures from Colin Barker, Mar 25 2018: (Start)

G.f.: x*(1 + 2*x - 2*x^2 - x^3 + x^4) / ((1 - x)^2*(1 - x - x^2)).

a(n) = -4 + (2^(-n)*((1-sqrt(5))^n*(-5+2*sqrt(5)) + (1+sqrt(5))^n*(5+2*sqrt(5)))) / sqrt(5) - n for n>1.

(End)

Example

All solutions for n=3:
  0 0   0 0   0 0   0 0   1 0   0 1   1 1   0 0   1 0   1 1   1 1
  0 0   0 1   1 0   1 1   1 0   0 1   1 0   1 1   1 1   0 1   0 1
  1 1   1 1   1 1   1 1   1 1   1 1   1 1   0 1   0 1   0 1   1 1

Crossrefs

Cf. A023548. - R. J. Mathar, Aug 06 2009

Sequence in context: A298785 A163787 A166863 * A131898 A168642 A357750

Adjacent sequences: A163701 A163702 A163703 * A163705 A163706 A163707

Keyword

nonn

Author

R. H. Hardin, Aug 03 2009

Status

approved