DIRECTED COLUMN-CONVEX POLYOMINOES BY RECURRENCE RELATIONS

In the literature most counting problems for directed columnconvex polyominoes are solved by using Schutzenberger's method. In this paper, we use the traditional recurrence relation approach in order to count the number of directed column-convex polyominoes with a given area, the number of their columns and the number of directed columnconvex polyominoes having at most κ cells in the first column. This approach allows us to state a very simple algorithm for the random generation of directed column-convex polyominoes. Furthermore, directed column-convex polyominoes are considered to be structures for storing and retrieving information in a computer, and their average internal path length is then evaluated.