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

Author

R. H. Hardin, Aug 03 2009

Keywords

• nonn

Examples

			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
		

Links

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

Crossrefs

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

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)