login
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.
92

%I #16 Feb 08 2024 08:19:54

%S 1,15,147,1231,9539,70679,509019,3596367,25070707,173088903,

%T 1186544331,8090866303,54950124515,372067098167,2513408596923,

%U 16948369098159,114128268554323,767705581586151,5159843165163435,34657637020377055,232672006452068291,1561421588852637335

%N 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.

%H Andrew Howroyd, <a href="/A069417/b069417.txt">Table of n, a(n) for n = 1..500</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (13,-48,40,-8).

%F From _Andrew Howroyd_, Oct 27 2020: (Start)

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

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

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

%F (End)

%e From _Andrew Howroyd_, Oct 27 2020: (Start)

%e Some of the a(2) = 15 arrays are:

%e 1 0 1 0 1 0 1 1 1 0

%e 1 1 1 0 1 1 1 1 1 1

%e 1 0 1 1 1 1 1 1 0 1

%e (End)

%t LinearRecurrence[{13, -48, 40, -8}, {1, 15, 147, 1231}, 25] (* _Paolo Xausa_, Feb 08 2024 *)

%o (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

%Y 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.

%K nonn,easy

%O 1,2

%A _R. H. Hardin_, Mar 22 2002

%E Terms a(12) and beyond from _Andrew Howroyd_, Oct 27 2020