In this paper we study some relevant prefixes of coloured Motzkin walks (otherwise called coloured Motzkin words). In these walks, the three kinds of step can have α,β and γ colours, respectively. In particular, when α=β=γ=1 we have the classical Motzkin walks while for α=γ=1 and β=0 we find the well-known Dyck walks. By using the concept of Riordan arrays and probability generating functions we find the average length of the relevant prefix in a walk of length n and the corresponding variance in terms of α,β and γ. This result is interesting from a combinatorial point of view and also provides an average case analysis of algorithms related to the problem of ranking and generating uniformly at random the coloured Motzkin words.

The relevant prefixes of coloured Motzkin words / D. Merlini; R. Sprugnoli. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 411:(2010), pp. 148-163. [10.1016/j.tcs.2009.09.021]

The relevant prefixes of coloured Motzkin words

MERLINI, DONATELLA;SPRUGNOLI, RENZO
2010

Abstract

In this paper we study some relevant prefixes of coloured Motzkin walks (otherwise called coloured Motzkin words). In these walks, the three kinds of step can have α,β and γ colours, respectively. In particular, when α=β=γ=1 we have the classical Motzkin walks while for α=γ=1 and β=0 we find the well-known Dyck walks. By using the concept of Riordan arrays and probability generating functions we find the average length of the relevant prefix in a walk of length n and the corresponding variance in terms of α,β and γ. This result is interesting from a combinatorial point of view and also provides an average case analysis of algorithms related to the problem of ranking and generating uniformly at random the coloured Motzkin words.
411
148
163
D. Merlini; R. Sprugnoli
File in questo prodotto:
File Dimensione Formato  
r32.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: DRM non definito
Dimensione 1.09 MB
Formato Adobe PDF
1.09 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/369020
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact