A094170 Number of quasi-triominoes in an n X n bounding box.

0, 0, 1, 10, 33, 88, 187, 360, 625, 1024, 1581, 2350, 3361, 4680, 6343, 8428, 10977, 14080, 17785, 22194, 27361, 33400, 40371, 48400, 57553, 67968, 79717, 92950, 107745, 124264, 142591, 162900, 185281, 209920, 236913, 266458, 298657, 333720, 371755, 412984, 457521

Offset: 0

Author

Jon Wild, May 07 2004

Keywords

• nonn
• easy

Comments

A quasi-polyomino is a polyomino whose cells are not necessarily connected. For all m > 1 there are an infinite number of quasi-m-ominoes; a(n) counts the quasi-triomino (quasi-3-omino) equivalence classes (under translation, rotation by 90 degrees and vertical and horizontal symmetry) whose members fit into an n X n bounding box.

This is different from A082966 because that sequence considers these two (for example) as different ways of placing 3 counters on a 3 X 3 checkerboard:

---

-X-

X-X

and

-X-

X-X

---

whereas here they are the same quasi-polyomino.

a(n) can also be interpreted as the number of non-equivalent Game of Life patterns on an n X n board that have exactly 3 live cells, etc.

Examples

			Illustration of a(3), the 10 quasi-triominoes that fit into a 3 X 3 bounding box:
XXX -XX XX- X-X X-X XX- X-X X-X X-- X--
--- -X- --X X-- -X- --- --- --- -X- --X
--- --- --- --- --- --X X-- -X- --X -X-
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Erich Friedman, Illustration of initial terms
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-5,5,1,-3,1).

Crossrefs

Cf. A094171, A094172.

Programs

Mathematica

CoefficientList[Series[x^2 (x^5 + x^4 + 4 x^3 + 4 x^2 + 7 x + 1)/((1 - x)^5 (x + 1)^2), {x, 0, 50}], x] (* Vincenzo Librandi, Feb 17 2014 *)

PARI

Vec(-x^2*(x^5+x^4+4*x^3+4*x^2+7*x+1)/((x-1)^5*(x+1)^2) + O(x^100)) \\ Colin Barker, Feb 16 2014

Formula

a(n) = (1/32)*(6*n^4 - 12*n^3 + 32*n^2 - 58*n + 29 - (6*n-3)*(-1)^n). - Ralf Stephan, Dec 03 2004

G.f.: -x^2*(x^5+x^4+4*x^3+4*x^2+7*x+1) / ((x-1)^5*(x+1)^2). - Colin Barker, Feb 15 2014

Extensions

Corrected and extended by Jon Wild, May 11 2004

More terms from Colin Barker, Feb 16 2014