AN EXHAUSTIVE GENERATION ALGORITHM FOR CATALAN OBJECTS AND OTHERS

The paper presents a CAT generation algorithm for Dyck paths with fixed length n. It is the formalization of a method for the exhaustive generation of these paths which can be described by two equivalent strategies. The former uses a rooted tree, the latter lists the paths and provides a visit of the nodes of the tree, basing on three simple operations. These constructions are strictly connected with ECO method and can be encoded by a rule, very similar to the succession rule in ECO, with a finite number of labels for each n. Moreover, with a slight variation, this method can be generalized to other combinatorial classes like Grand Dyck or Motzkin paths.The paper presents a CAT generation algorithm for Dyck paths with fixed length n. It is the formalization of a method for the exhaustive generation of these paths which can be described by two equivalent strategies. The former uses a rooted tree, the latter lists the paths and provides a visit of the nodes of the tree, basing on three simple operations. These constructions are strictly connected with ECO method and can be encoded by a rule, very similar to the succession rule in ECO, with a finite number of labels for each n. Moreover, with a slight variation, this method can be generalized to other combinatorial classes like Grand Dyck or Motzkin paths.