In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^{j+1}0^j. By means of the theory of Riordan arrays, we solve the enumeration problem and 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.
Pattern 1^{j+1}0^j avoiding binary words / S. Bilotta; D. Merlini; E. Pergola; R. Pinzani. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - STAMPA. - 117:(2012), pp. 35-55. [10.3233/FI-2012-687]
Pattern 1^{j+1}0^j avoiding binary words
BILOTTA, STEFANO;MERLINI, DONATELLA;PERGOLA, ELISA;PINZANI, RENZO
2012
Abstract
In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^{j+1}0^j. By means of the theory of Riordan arrays, we solve the enumeration problem and 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.File | Dimensione | Formato | |
---|---|---|---|
r36.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
229.53 kB
Formato
Adobe PDF
|
229.53 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.