Saturated fully leafed tree-like polyforms and polycubes

DOI10.1016/J.JDA.2018.11.004MaRDI QIDQ1711661zbMATH OpenOpenAlexFDO

Authors Alexandre Blondin Massé, Julien de Carufel, Alain Goupil

Publication date 18 January 2019

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.09181

zbMATH Keywords

latticecombinatoricspolyominopolycubedynamic algorithmfully leafedpolyform

Mathematics Subject Classification ID

Polyominoes (05B50)

Abstract: We present recursive formulas giving the maximal number of leaves in tree-like polyforms living in two-dimensional regular lattices and in tree-like polycubes in the three-dimensional cubic lattice. We call these tree-like polyforms and polycubes emph{fully leafed}. The proof relies on a combinatorial algorithm that enumerates rooted directed trees that we call abundant. In the last part, we concentrate on the particular case of polyforms and polycubes, that we call emph{saturated}, which is the family of fully leafed structures that maximize the ratio $mbox(numberofleaves)/mbox(numberofcells)$. In the polyomino case, we present a bijection between the set of saturated tree-like polyominoes of size $4k+1$ and the set of tree-like polyominoes of size $k$. We exhibit a similar bijection between the set of saturated tree-like polycubes of size $41k+28$ and a family of polycubes, called $4$-trees, of size $3k+2$.

Recommendations

• Fully leafed tree-like polyominoes and polycubes
• The growth rate of high-dimensional tree polycubes
• Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes
• The growth rate of high-dimensional tree polycubes
• COUNTING d-DIMENSIONAL POLYCUBES AND NONRECTANGULAR PLANAR POLYOMINOES

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Procedure for Improving the Upper Bound for the Number of n-Ominoes
• Algebraic languages and polyominoes enumeration
• Combinatorial aspects of \(L\)-convex polyominoes
• Counting polyominoes: yet another attack
• Enumeration of polyominoes inscribed in a rectangle
• Enumeration of specific classes of polycubes
• Enumeration of three-dimensional convex polygons
• Enumerations of lattice animals and trees
• Fully leafed induced subtrees
• Fully leafed tree-like polyominoes and polycubes
• Generating convex polyominoes at random
• Leaf realization problem, caterpillar graphs and prefix normal words
• On directed-convex polyominoes in a rectangle
• Partially directed snake polyominoes
• Polygons, polyominoes and polycubes
• Statistics on parallelogram polyominoes and a \(q,t\)-analogue of the Narayana numbers
• The enumeration of tree-like polyhexes
• The site-perimeter of bargraphs

Cited in

(2)

• Fully leafed tree-like polyominoes and polycubes
• Non saturated polyhexes and polyiamonds

This page was built for publication: Saturated fully leafed tree-like polyforms and polycubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711661)