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.File | Dimensione | Formato | |
---|---|---|---|
r32.pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
1.09 MB
Formato
Adobe PDF
|
1.09 MB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.