2
E. BARCUCCI, S. BRUNETTI AND F. DEL RISTORO
objects. The objects having the same dimension with respect to the parameter p
are at the same level and the sons of an object correspond to the objects obtained
from it. We label each vertex by the number of its sons. We call this value the
fertility of the node (and of the corresponding object). If the labels of the sons
of a node labelled (k) only depend on the value k, we can represent the growing
process of a generating tree by means of the following notation (called succession
rule)
ꢀ
(b)
(k) → (c1)(c2) . . . (ck),
where (b) is the label of the root and ci is the label of the i-th son of a node
labelled (k). In such a way, a succession rule can succintly represent a generating
tree.
The aim of this paper is to show how variations on succession rules can influence
the nature of the corresponding generating function. In Section 2, we describe the
class of deco polyominoes that are enumerated by factorial numbers with respect
to their directed height and we examine the succession rule which describes the
construction of the class obtained by using the ECO method. In the subsequent
sections, we illustrate some succession rules obtained by changing the previous
one: the polyomino classes related to these rules are deco polyomino subclasses,
enumerated by the Bell, Catalan and odd index Fibonacci numbers. We also study
the classes according to their directed height and width, and we find some other
well-known numbers. As a result we provide some new combinatorial interpreta-
tions of the relations that link these sequences of numbers to the previous ones.
In treating the succession rules, we can virtually forget the combinatorial objects
themselves. All the succession rules we studied are of the kind
ꢀ
(2)
(k) → (c1)(c2) . . . (ck),
where 2 ≤ ci ≤ ci+1 (i = 1, . . . , k − 1) and ck = k + 1. By simply making some
changes in the succession rules, we find some generating functions that are very
different from the original ones and also highly vary among themselves, since they
are transcendental (Sects. 2, 3), algebraic (Sect. 4) and rational (Sect. 5).
2. The factorial succession rule
2
We introduce some definitions. Consider the R plane; a cell is a unitary square
[i, i+1]×[j, j+1], i, j ∈ N, and a polyomino is a connected set of pairs of cells having
one side in common. The polyominoes are defined up to a translation. We can
obtain a directed polyomino by starting out from a cell called source and by adding
other cells in predetermined directions, such East and North, that is, to the right
of or over existing cells. In this way, a polyomino grows in a preferred direction. A
column (row) is the intersection of a polyomino with an infinite vertical (horizontal)
strip [i, i+1]×R (R×[j, j +1]). A directed column-convex polyomino is a directed