Catalan-like Numbers and Succession Rules

Luca Ferrari and Renzo Pinzani

Dipartimento di Matematica “R. Magari", Via del Capitano 15, 53100 Siena, Italy

Dipartimento di Sistemi e Informatica, via Lombroso 6/17, 50134 Firenze, Italy

ferrari@math.unifi.it pinzani@dsi.unifi.it

Abstract. Full Text PDF

The ECO method was founded in the 90’s by a group of researchers, including Pinzani, Barcucci, Del Lungo and Pergola [4,5]. It consists of a purely combinatorial way of constructing the objects of a given class in such a way that, if the construction is sufficiently regular and recursive, enumeration follows by more or less standard methods of combinatorial analysis. More precisely, one starts by partitioning a class of objects according to their size (suitably defined). The goal is then to perform a sort of local expansion on each object of a given size, thus producing all the objects of the successive size exactly once. Therefore a single object produces a set of objects according to some parameter. Typically, if such a construction is regular enough, one can encode it using a succession rule [9,10], which is a purely formal system, generally expressed as follows:

(1)

Here the letters denote positive integers, is called the axiom and is the production of . A succession rule can be represented by means of its generating tree, which is, by definition, the infinite, rooted, labelled tree whose root is labelled (like the axiom) and such that every node labelled produces sons, labelled respectively . One of the main enumerative information provided by a succession rule is the numerical sequence of the cardinalities of the levels of the generating tree associated with the rule.

The basic reference for the ECO method is [4], in which many examples can also be found.

The importance of succession rules as a tool for the ECO method has lead to several investigations to get a better mathematical insight on them. In [7] the authors define the concept of rule operator, thus translating a succession rule into a linear operator on one-variable polynomials. In [6] every succession rule is associated with at least two infinite matrices: the production matrix, which is essentially the matrix of the related rule operator with respect to the canonical basis of polynomials , and the ECO matrix, whose -entry is, by definition, the number of nodes labelled at level in the corresponding generating tree. The latter matrix has been considered also in [8], where it is called “AGT matrix", whereas a few instances of the former one appeared for the first time in [9] under the name of “transfer matrices".

Another combinatorial theory dealing with infinite matrices is

In [2,3] Aigner extends this theory by considering a more general kind of matrices, which we will rename Aigner matrices (instead of the infelicitous name “recursive matrices" used in [3]). Generalizing the previous definition, we will call Catalan-like numbers every sequence appearing as the first column of an Aigner matrix.

The aim of our work is to provide a “vocabulary" to translate the ECO method into Aigner’s theory, and vice versa. Such a vocabulary turns out to be based on linear algebra tools, consisting of a suitable change of basis in the vector space of one variable polynomials. What we hope to show is that the two theories under consideration are, in some algebraic sense, the two sides of the same medal, which is quite surprising if we think of the very different starting points, and combinatorial meanings, of such theories.

After a brief survey of the notions we need from the ECO method and Aigner’s theory, we provide the main linear algebra tools for our purposes. In particular, we define the Aigner basis in the vector space of one variable polynomials and prove some of its properties. Next we introduce what we call the fundamental change of basis, which is the key ingredient to accomplish our project, and propose some examples to illustrate our approach. The final part of the work is devoted to the study of two particular cases, for which we are able to fully describe how to switch from one theory to the other. We conclude by giving some hints for possible, future works.

References

[1] M. Aigner Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999) 33-51.

[2] M. Aigner A characterization of the Bell numbers, Discrete Math. 205 (1999) 207-210.

[3] M. Aigner Catalan and other numbers: a recurrent theme, in: H. Crapo, D. Senato (Eds.), Algebraic Combinatorics and Computer Science, Springer, Milano, 2001, 347-390.

[4] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani ECO: a methodology for the enumeration of combinatorial objects, J. Differ. Equations Appl. 5 (1999) 435-490.

[5] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani A methodology for plane tree enumeration, Discrete Math. 180 (1998) 45-64.

[6] E. Deutsch, L. Ferrari, S. Rinaldi Production matrices, preprint.

[7] L. Ferrari, R. Pinzani A linear operator approach to succession rules, Linear Algebra Appl. 348 (2002) 231-246.

[8] D. Merlini, M. C. Verri Generating trees and proper Riordan arrays, Discrete Math. 218 (2000) 167-183.

[9] J. West Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995) 247-262.

[10] J. West Generating trees and forbidden subsequences, Discrete Math. 157 (1996) 363-374.