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.

AN EXHAUSTIVE GENERATION ALGORITHM FOR CATALAN OBJECTS AND OTHERS / A. Bernini; I. Fanti; E. Grazzini. - In: PURE MATHEMATICS AND APPLICATIONS. - ISSN 1218-4586. - STAMPA. - 17 (1-2):(2006), pp. 39-53.

AN EXHAUSTIVE GENERATION ALGORITHM FOR CATALAN OBJECTS AND OTHERS

BERNINI, ANTONIO;GRAZZINI, ELISABETTA
2006

Abstract

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.
2006
17 (1-2)
39
53
A. Bernini; I. Fanti; E. Grazzini
File in questo prodotto:
File Dimensione Formato  
Puma 17(2).pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: DRM non definito
Dimensione 255.15 kB
Formato Adobe PDF
255.15 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/315689
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact