A054421 Number of disconnected 3 X n binary matrices.

0, 1, 11, 102, 882, 7295, 58533, 459484, 3547860, 27043405, 204016879, 1526141666, 11336059046, 83703379691, 614911337833, 4497505562616, 32769214114664, 237956784843737, 1722809101653651, 12440161483566494, 89616141395864986, 644202131570116247

Offset

1,3

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

Table of n, a(n) for n=1..22.

Index entries for linear recurrences with constant coefficients, signature (14,-52,26,-35).

Formula

a(n) = 14*a(n-1)-52*a(n-2)+26*a(n-3)-35*a(n-4). G.f.: -x^2*(3*x-1) / ((7*x-1)*(5*x^3-3*x^2+7*x-1)). - Colin Barker, Jan 13 2014

Prog

(PARI) Vec(-x^2*(3*x-1)/((7*x-1)*(5*x^3-3*x^2+7*x-1)) + O(x^100)) \\ Colin Barker, Jan 13 2014

Crossrefs

Cf. A054417-A054420. 4*A054421(n) + 2*A054419(n) + A054420(n) = 7^n.

Sequence in context: A100580 A253631 A087744 * A037700 A037609 A055150

Adjacent sequences: A054418 A054419 A054420 * A054422 A054423 A054424

Keyword

nonn,easy

Author

N. J. A. Sloane, May 22 2000

Extensions

More terms from James A. Sellers, May 23 2000

More terms from Colin Barker, Jan 13 2014

Status

approved