A188707 Number of 3 X n binary arrays without the pattern 0 0 diagonally or vertically.

5, 21, 90, 387, 1665, 7164, 30825, 132633, 570690, 2455551, 10565685, 45461772, 195611805, 841673709, 3621533130, 15582644523, 67048623225, 288495182556, 1241330043105, 5341164667857, 22981833209970, 98885672046279

Offset: 1

Author

R. H. Hardin, Apr 08 2011

Keywords

• nonn
• easy

Comments

Row 3 of A188706.

Examples

			Some solutions for 3 X 3:
  1 1 0    1 0 0    1 1 0    1 0 0    0 0 0    1 0 0    0 0 1
  1 1 1    1 1 1    1 0 1    1 1 1    1 1 1    1 1 1    1 1 1
  1 0 1    1 1 0    0 1 1    0 0 1    0 0 1    1 1 1    0 1 1
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..200
• C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), #12.7.8.
• Index entries for linear recurrences with constant coefficients, signature (5,-3).

Programs

Mathematica

LinearRecurrence[{5, -3}, {5, 21}, 22] (* Robert G. Wilson v, Jul 13 2011 *)

PARI

\\ using formula by John M. Campbell
a(n)=my(v=[1,1;1,4]^(n-1)*[1,2]~); v[1]*1+v[2]*2; \\ Joerg Arndt, Mar 19 2021

Formula

a(n) = 5*a(n-1) - 3*a(n-2).

a(n) = [1,1;1,4]^(n-1).{1,2}.{1,2}. - John M. Campbell, Jul 09 2011

G.f.: x*(5 - 4*x)/(1 - 5*x + 3*x^2). - Colin Barker, Mar 11 2012