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

1, 17, 197, 1985, 18621, 167337, 1461797, 12519345, 105683341, 882516857, 7308428597, 60131384705, 492202181661, 4012347269577, 32599584662597, 264152863210065, 2135714594033581, 17236446198921497, 138901692341235797, 1117982939085627425, 8989229069675479101

Offset: 1

Author

R. H. Hardin, Mar 22 2002

Keywords

• nonn
• easy

Examples

			The 17 binary arrays for n=2:
01 10 01 10 01 10 01 10 01 10 11 11 11 11 11 11 11
01 10 01 10 11 11 11 11 11 11 01 10 01 01 11 11 11
01 10 11 11 01 10 10 01 11 11 01 10 11 11 01 10 11 - _R. J. Mathar_, Jun 21 2023
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (15,-58,16).

Crossrefs

Row 3 of A359576.

Cf. 1 X n A000225, 2 X n A005061, n X 2 A001333, 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

CoefficientList[Series[(-2 z - 1)/(16 z^3 - 58 z^2 + 15 z - 1), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 24 2011 *)

PARI

x='x+O('x^30); Vec(x*(1+2*x)/((1-8*x)*(2*x^2-7*x+1))) \\ G. C. Greubel, Apr 22 2018

Formula

G.f.: x*(1+2*x)/((1-8*x)*(2*x^2-7*x+1)). - Vladeta Jovovic, Jul 02 2003

From Maksym Voznyy (voznyy(AT)mail.ru), Jul 25 2008: (Start)

a(n) = 15*a(n-1) - 58*a(n-2) + 16*a(n-3), where a(1)=1, a(2)=17, a(3)=197;

a(n) = 8^n + 1/sqrt(41)*4^(n+1)*((7+sqrt(41))^(-(n+1)) - (7-sqrt(41))^(-(n+1))). (End)

a(n) = 8^n - A186446(n). - R. J. Mathar, Jan 27 2020