A263053 Number of (n+1) X 2 0..1 arrays with each row and column not divisible by 3, read as a binary number with top and left being the most significant bits.

2, 2, 10, 10, 42, 42, 170, 170, 682, 682, 2730, 2730, 10922, 10922, 43690, 43690, 174762, 174762, 699050, 699050, 2796202, 2796202, 11184810, 11184810, 44739242, 44739242, 178956970, 178956970, 715827882, 715827882, 2863311530, 2863311530, 11453246122, 11453246122

Offset

1,1

Comments

Each row must be either 01 or 10. The two columns are therefore binary complements with sum 2^k-1, where k = n + 1 is the number of rows. If k is even then 2^k-1 is divisible by 3 and the number of solutions is 2*(2^k-1)/3. If k is odd then 2^k-1 == 1 (mod 3) and the number of solutions is (2^k-2)/3. - Andrew Howroyd, Feb 03 2022

Links

Paolo Xausa, Table of n, a(n) for n = 1..3000 (terms 1..210 from R. H. Hardin).

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

Formula

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

From Colin Barker, Jan 01 2019: (Start)

G.f.: 2*x / ((1 - x)*(1 - 2*x)*(1 + 2*x)).

a(n) = 2^n - 2/3 - (-2)^n/3. (End)

a(n) = 2*A052992(n-1). - Pascal Bisson, Feb 03 2022

Example

All solutions for n=4:
  0 1   0 1   1 0   1 0   1 0   0 1   1 0   1 0   0 1   0 1
  0 1   0 1   0 1   1 0   0 1   1 0   1 0   0 1   1 0   1 0
  1 0   0 1   0 1   1 0   1 0   1 0   0 1   1 0   0 1   0 1
  0 1   1 0   0 1   0 1   1 0   1 0   1 0   0 1   1 0   0 1
  1 0   0 1   1 0   1 0   1 0   0 1   0 1   0 1   1 0   0 1

Mathematica

LinearRecurrence[{1, 4, -4}, {2, 2, 10}, 40] (* Paolo Xausa, Sep 14 2025 *)

Prog

(Python) [int(2**n - 2/3 -((-2)**n)/3) for n in range(1, 40)] # Pascal Bisson, Feb 03 2022
(PARI) a(n)=2^n-2/3-(-2)^n/3 \\ Charles R Greathouse IV, May 28 2026

Crossrefs

Column 1 of A263060.

Cf. A052992.

Sequence in context: A391929 A147801 A367545 * A361835 A066965 A066966

Adjacent sequences: A263050 A263051 A263052 * A263054 A263055 A263056

Keyword

nonn,easy,changed

Author

R. H. Hardin, Oct 08 2015

Status

approved