A163733 Number of n X 2 binary arrays with all 1's connected, all corners 1, and no 1 having more than two 1's adjacent.

1, 1, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset

1,3

Comments

Same recurrence for A163695.

Same recurrence for A163714.

Appears to coincide with diagonal sums of A072405. - Paul Barry, Aug 10 2009

From Gary W. Adamson, Sep 15 2016: (Start)

Let the sequence prefaced with a 1: (1, 1, 1, 2, 2, 4, 6, ...) equate to r(x). Then (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) = the Fibonacci sequence, (1, 1, 2, 3, 5, ...). Let M = the following production matrix:

1, 0, 0, 0, 0, ...

1, 0, 0, 0, 0, ...

1, 1, 0, 0, 0, ...

2, 1, 0, 0, 0, ...

2, 1, 1, 0, 0, ...

4, 2, 1, 0, 0, ...

6, 2, 1, 1, 0, ...

...

Limit of the matrix power M^k as k->infinity results in a single column vector equal to the Fibonacci sequence. (End)

Apparently a(n) = A128588(n-2) for n > 3. - Georg Fischer, Oct 14 2018

Links

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

Formula

Empirical: a(n) = a(n-1) + a(n-2) for n >= 5.

G.f.: (1-x^3)/(1-x-x^2) (conjecture). - Paul Barry, Aug 10 2009

a(n) = round(phi^(k-1)) - round(phi^(k-1)/sqrt(5)), phi = (1 + sqrt(5))/2 (conjecture). - Federico Provvedi, Mar 26 2013

G.f.: 1 + 2*x - x*Q(0), where Q(k) = 1 + x^2 - (2*k+1)*x + x*(2*k-1 - x)/Q(k+1); (conjecture), (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013

G.f.: If prefaced with a 1, (1, 1, 1, 2, 2, 4, ...): (1 - x^2 - x^4)/(1 - x - x^2); where the modified sequence satisfies A(x)/A(x^2), A(x) is the Fibonacci sequence. - Gary W. Adamson, Sep 15 2016

Example

All solutions for n=8:
   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1
   0 1   1 0   1 0   1 0   1 0   1 0   0 1   0 1   0 1   0 1
   0 1   1 0   1 0   1 0   1 1   1 0   0 1   0 1   1 1   0 1
   0 1   1 0   1 0   1 1   0 1   1 0   0 1   0 1   1 0   1 1
   0 1   1 0   1 1   0 1   0 1   1 0   0 1   1 1   1 0   1 0
   0 1   1 0   0 1   0 1   0 1   1 1   1 1   1 0   1 0   1 0
   0 1   1 0   0 1   0 1   0 1   0 1   1 0   1 0   1 0   1 0
   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1
------
   1 1   1 1   1 1   1 1   1 1   1 1
   0 1   0 1   0 1   1 0   1 0   1 0
   1 1   1 1   0 1   1 0   1 1   1 1
   1 0   1 0   1 1   1 1   0 1   0 1
   1 1   1 0   1 0   0 1   0 1   1 1
   0 1   1 1   1 1   1 1   1 1   1 0
   0 1   0 1   0 1   1 0   1 0   1 0
   1 1   1 1   1 1   1 1   1 1   1 1

Mathematica

Join[{1, 1}, Table[2*Fibonacci[n], {n, 70}]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2012 *)
Table[Round[GoldenRatio^(k-1)] - Round[GoldenRatio^(k-1)/Sqrt[5]], {k, 1, 70}] (* Federico Provvedi, Mar 26 2013 *)

Crossrefs

Cf. A118658, A055389, A006355, A006355, A169985, A000045.

Cf. A128588. - Georg Fischer, Oct 14 2018

Sequence in context: A293633 A006355 A055389 * A198834 A270925 A331964

Adjacent sequences: A163730 A163731 A163732 * A163734 A163735 A163736

Keyword

nonn

Author

R. H. Hardin, Aug 03 2009

Status

approved