A054419 Number of connected 3 X n binary matrices (divided by 2).

3, 21, 143, 953, 6347, 42285, 281719, 1876913, 12504659, 83310469, 555043871, 3697898985, 24636713627, 164138517789, 1093548978567, 7285610864737, 48539321706403, 323386164243445, 2154513238908591, 14354130788161817

Offset

1,1

Comments

A connected (0,1) matrix is one where you can get from any black square, i.e. 1, to any other by chess king moves.

References

R. Levy and J. Shapiro, Uniqueness in paint-by-numbers puzzles, preprint, 2000.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (7, -3, 5).

Formula

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

G.f.: (-5*x^2-3)/(5*x^3-3*x^2+7*x-1). - Harvey P. Dale, Nov 23 2011

Mathematica

LinearRecurrence[{7, -3, 5}, {3, 21, 143}, 40] (* Harvey P. Dale, Nov 23 2011 *)

Prog

(Magma) I:=[3, 21, 143]; [n le 3 select I[n] else 7*Self(n-1)-3*Self(n-2)+5*Self(n-3): n in [1..20]]; // Vincenzo Librandi, Feb 14 2012

Crossrefs

Cf. A054417-A054421.

Number of connected 3 X n binary matrices = 2*A054419 = 4*A054417 + 2*A054418.

Sequence in context: A303349 A337467 A318041 * A228115 A377096 A033888

Adjacent sequences: A054416 A054417 A054418 * A054420 A054421 A054422

Keyword

nonn,easy

Author

N. J. A. Sloane, May 22 2000

Extensions

More terms from James A. Sellers, May 23 2000

Status

approved