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.
2012
117
35
55
S. Bilotta; D. Merlini; E. Pergola; R. Pinzani
File in questo prodotto:
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.

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