An Introduction to Dendrominos

N. Lygeros, J. Scoville




This article deals with a special class of polyominos - the undivided polyominos of minimal area.  More intuitively, these polyominos form unbranched chains with distinct ends.  The area, A, and perimeter, P, of such a  polyomino are related by P=2(A+1).  Since the dual of a polyomino in a square lattice is a tree, we shall call these constructions dendrominos.   The boundaries of a dendromino are the cells whose maxima in the dual tree are of degree one.  A dendromino of n>1 cells has exactly two boundary cells.   Examples of dendrominos follow:

                               

Figure 1:  Dendrominos

The rightmost dendromino is a member of a special class of dendromino.  Since no cells may be added to produce a larger dendromino, we say that it is a terminal dendromino.  A minimal terminal dendromino is a terminal dendromino with a minimal number of cells.  The rightmost dendromino above is a two dimensional minimal terminal dendromino, consisting of 19 cells.  In three dimensions, the minimal terminal dendromino has 23 cells:

Figure 2: The 3-d minimal terminal dendromino has 23 cells.

Since the n-cube tiles n-space, the concept of a cubic dendromino extends naturally to higher dimensions.  In general, the minimal terminal dendromino in n dimensions has 8n-1 cells.  A minimal arrangement is produced when cells are placed at positions +/- 1 on the x-axis and at +/- 2 on every axis.  These cells are then connected by minimal paths to form a dendromino.  The z-w cross-sections of the 4-d minimal terminal dendromino follow:

  x=-2 x=-1 x=0 x=1 x=2
y=2 .....
.....
.....
.....
.....
.....
.....
.....
.....
.....
..X..
..X..
..XXX
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
y=1 .....
.....
.....
.....
.....
.....
.....
.....
.....
.....
..X..
.....
....X
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
y=0 .....
.....
XXX..
.....
.....
.....
.....
X.X..
.....
.....
XXX..
X....
X...X
.....
..X..
.....
.....
..X..
.....
..X..
.....
.....
..X..
..X..
..X..
y=-1 .....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
....X
.....
..X..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
y=-2 .....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
....X
....X
..XXX
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

Figure 3: A 4-d minimal terminal dendromino has 31 cells.

Terminal dendrominos with k cells exist for all k>18 in two dimensions.  These may be constructed by adding cells in multiples of two to the 19- and 20-celled dendrominos.  In three dimensions, terminal dendrominos exist for all k>29.   It is unknown whether even terminal dendrominos exist in three dimensions for k<30.

Images/144_dend4.gif (1587 bytes)                         Images/144_dend5.gif (1648 bytes)

21-celled dendromino                                         22-celled dendromino

Dendrominos are not, in lower dimensions, restricted to a cubic lattice.  In two dimensions, for example, dendrominos can also exist in triangular and hexagonal lattices.  The minimal terminal dendromino in a hexagonal lattice has 13 cells, and the minimal terminal dendromino in a triangular lattice has 20 cells.

The maximal filling of an n-cube of side length k (where k is odd) with a dendromino is 2((k+1)/2)^n-1 cells.  In two dimensions, it is possible to obtain a maximal filling with a terminal dendromino. 

Special thanks are extended to Jim Ferry for mathematical contributions and to Jennifer Kasten for translation services.

References:

N. Madras, C.E. Soteros, S.G. Whittington, J.L. Martin, M.F. Sykes, S. Flesia and D.S. Gaunt : The free energy of a collapsing branched polymer.  Journal of Physics A:  Mathematical and General, 23, p.5327-5350. 1990.

S. Flesia, D.S. Gaunt, C.E. Soteros, S.G. Whittington : Statistics of collapsing lattice animals. Journal of Physics A:              Mathematical and General, 27, p.5831-5846. 1994

R. Stanley : Enumerative Combinatorics. Cambridge University Press 1997.







free counters


Opus