A069417 Number of 3 X n binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row.

1, 15, 147, 1231, 9539, 70679, 509019, 3596367, 25070707, 173088903, 1186544331, 8090866303, 54950124515, 372067098167, 2513408596923, 16948369098159, 114128268554323, 767705581586151, 5159843165163435, 34657637020377055, 232672006452068291, 1561421588852637335

Offset: 1

Author

R. H. Hardin, Mar 22 2002

Keywords

• nonn
• easy

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Index entries for linear recurrences with constant coefficients, signature (13,-48,40,-8).

Crossrefs

Cf. 2 X n A001047, n X 2 A034182, 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.

Programs

Mathematica

LinearRecurrence[{13, -48, 40, -8}, {1, 15, 147, 1231}, 25] (* Paolo Xausa, Feb 08 2024 *)

PARI

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

Formula

From Andrew Howroyd, Oct 27 2020: (Start)

a(n) = A069361(n) - 2*A069396(n).

a(n) = 13*a(n-1) - 48*a(n-2) + 40*a(n-3) - 8*a(n-4) for n > 4.

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

(End)

Extensions

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