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,1

Comments

Row 3 of A188706.

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).

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

Example

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

Mathematica

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

Prog

(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

Crossrefs

Sequence in context: A273796 A035011 A113987 * A360580 A333538 A164037

Adjacent sequences: A188704 A188705 A188706 * A188708 A188709 A188710

Keyword

nonn,easy

Author

R. H. Hardin, Apr 08 2011

Status

approved