A069429 Half the number of 3 X n binary arrays with no path of adjacent 1's or adjacent 0's from top row to bottom row.

3, 16, 84, 440, 2304, 12064, 63168, 330752, 1731840, 9068032, 47480832, 248612864, 1301753856, 6816071680, 35689414656, 186872201216, 978475548672, 5123364487168, 26826284728320, 140464250421248, 735480363614208, 3851025180000256, 20164229625544704, 105581277033267200

Offset: 1

Author

R. H. Hardin, Mar 22 2002

Keywords

• nonn
• easy

Examples

			From _Andrew Howroyd_, Oct 27 2020: (Start)
Some of the 2*a(2) = 32 arrays are:
  0 0   0 0   0 0   0 1   0 1   0 0   0 1
  0 0   0 1   1 1   1 0   1 0   1 1   1 0
  1 1   1 1   1 1   1 1   0 1   0 0   1 1
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (6,-4).

Crossrefs

Cf. 2 X n A000079, n X 1 A000225, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

Cf. A084326.

Programs

Mathematica

LinearRecurrence[{6, -4}, {3, 16}, 100] (* Jean-François Alcover, Nov 01 2020 *)

PARI

Vec((3 - 2*x)/(1 - 6*x + 4*x^2) + O(x^30)) \\ Andrew Howroyd, Oct 27 2020

PARI

a(n) = 2^(n-1)*fibonacci(2*n+2) \\ Andrew Howroyd, Oct 27 2020

Formula

Empirical G.f.: x*(3-2*x)/(1-6*x+4*x^2). - Colin Barker, Feb 22 2012

Empirical: a(n) = 3*A084326(n) - 2*A084326(n-1). - R. J. Mathar, Nov 09 2018

From Andrew Howroyd, Oct 27 2020: (Start)

The above conjectures are true and follow from formulas given in A069361 and A069396.

a(n) = (8^n)/2 - A069361(n) + A069396(n).

a(n) = 2^(n-1)*Fibonacci(2*n+2) = A084326(n+1)/2. (End)

Extensions

Terms a(21) and beyond from Andrew Howroyd, Oct 27 2020