In this paper we study the construction and the enumeration of particular binary words avoiding a primitive Dyck word. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern. Then, we give the generating function of such words according to the number of ones. Finally, a more general algorithm that generates binary words avoiding a set of primitive Dyck words is given.
Primitive Dyck words as an invariance class for pattern avoidance / Bilotta, Stefano; Grazzini, Elisabetta; Pergola Elisa. - ELETTRONICO. - (2012), pp. 1-10. (Intervento presentato al convegno GASCom 2012 tenutosi a Bordeaux, Francia nel 25/06/2012 - 27/06/2016).
Primitive Dyck words as an invariance class for pattern avoidance
BILOTTA, STEFANO;GRAZZINI, ELISABETTA;PERGOLA, ELISA
2012
Abstract
In this paper we study the construction and the enumeration of particular binary words avoiding a primitive Dyck word. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern. Then, we give the generating function of such words according to the number of ones. Finally, a more general algorithm that generates binary words avoiding a set of primitive Dyck words is given.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.