A228661 Number of 2 X n binary arrays with top left value 1 and no two ones adjacent horizontally, diagonally or antidiagonally.

2, 2, 8, 14, 38, 80, 194, 434, 1016, 2318, 5366, 12320, 28418, 65378, 150632, 346766, 798662, 1838960, 4234946, 9751826, 22456664, 51712142, 119082134, 274218560, 631464962, 1454120642, 3348515528, 7710877454, 17756424038, 40889056400

Offset

1,1

Comments

Row 2 of A228660.

The recurrence is demonstrated as follows: For every 2X(n-1) array, we can add the column (0,0) to get an appropriate array of size 2Xn, and for every 2X(n-2) array, we can add the column (0,0) and either (1,0), (0,1) or (1,1) to get an appropriate sized array. Every admissible array is of one of these two forms, and these two forms do not overlap (since their last columns are different). - Tom Edgar, Aug 29 2013

Links

R. H. Hardin, Table of n, a(n) for n = 1..210

Index entries for linear recurrences with constant coefficients, signature (1,3).

Formula

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

G.f.: -2*x / ( -1+x+3*x^2 ). a(n) = 2*A006130(n-1). - R. J. Mathar, Aug 29 2013

a(n) = -2/13*sqrt(13)*(-1/2*sqrt(13)+1/2)^n + 2/13*sqrt(13)*(1/2*sqrt(13)+1/2)^n. - Tom Edgar, Aug 31 2013

G.f.: Q(0)/x -1/x, where Q(k) = 1 + 3*x^2 + (2*k+3)*x - x*(2*k+1 + 3*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013

Example

Some solutions for n=4
..1..0..1..0....1..0..0..0....1..0..0..1....1..0..0..0....1..0..1..0
..1..0..1..0....1..0..0..0....1..0..0..0....0..0..1..0....0..0..0..0

Crossrefs

Sequence in context: A045677 A280399 A005633 * A369316 A026585 A229730

Adjacent sequences: A228658 A228659 A228660 * A228662 A228663 A228664

Keyword

nonn

Author

R. H. Hardin, Aug 29 2013

Status

approved