A131482 a(n) is the number of free n-celled tree-shaped polyominoes.

1, 1, 2, 4, 11, 27, 83, 255, 847, 2829, 9734, 33724, 118245, 416816, 1478602, 5267171, 18840144, 67611472, 243378415, 878407170, 3178068821, 11523323634, 41865833602, 152382134767

Offset

1,3

Comments

a(n) is the number of n-celled tree-shaped polyominoes, that is, the polyominoes that have a tree as their connectedness graph (vertices of this graph correspond to cells and two vertices are connected if the corresponding cells have a common edge). These are precisely the polyominoes with perimeter 2n+2, which is the maximal perimeter of an n-celled polyomino.

Links

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

Andrew Clarke, Isoperimetrical Polyominoes, The Poly Pages.

Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).

Formula

a(n) <= A000105(n), a(n) <= A057730(n+1).

a(n) >= A000602(n) [see comment on edge graph trees]. - R. J. Mathar, Mar 08 2021

Example

For n = 4, out of A000105(4) = 5 tetrominoes, all but one (the 2 x 2 square) are tree-like, so a(4) = 4.

Crossrefs

Cf. A000105, A057730. Diagonal of A342243.

A350030 (resp. A359522) counts only polyominoes without holes (resp. with holes).

A002013 counts only unbranched polyominoes.

A038142 is the analog for polyhexes (perimeter 4n+2), A304196 is the analog for polycubes (surface area 4n+2).

Cf. A066158 (fixed).

Sequence in context: A319616 A148130 A350030 * A234845 A148131 A234844

Adjacent sequences: A131479 A131480 A131481 * A131483 A131484 A131485

Keyword

nonn,hard,more

Author

Tanya Khovanova, Jul 27 2007

Extensions

a(14)-a(16) from David Radcliffe, Dec 25 2017

a(17) from David Radcliffe, Dec 26 2017

a(18)-a(24) from John Mason, Dec 11 2021

Edited by Andrei Zabolotskii, Nov 23 2025

Status

approved