The relevant prefixes of coloured Motzkin walks: an average case analysis

DOI10.1016/j.tcs.2009.09.021zbMath1189.68181OpenAlexW2048233076WikidataQ60692282 ScholiaQ60692282MaRDI QIDQ1041231

Donatella Merlini, Renzo Sprugnoli

Publication date: 1 December 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.021

zbMATH Keywords

rankingprobability generating functionsrandom generationaverage case analysiscoloured Motzkin walks

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items (5)

An application of Riordan arrays to the transient analysis of \(M/M/1\) queues ⋮ Combinatorics of Riordan arrays with identical \(A\) and \(Z\) sequences ⋮ A symbolic treatment of Riordan arrays ⋮ Bijections of Motzkin paths using shifted Riordan decompositions ⋮ Combinatorial matrices derived from generalized Motzkin paths

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Riordan group
• Underdiagonal lattice paths with unrestricted steps
• Random generation of trees and other combinatorial objects
• A calculus for the random generation of labelled combinatorial structures
• Riordan arrays and combinatorial sums
• Uniform generation of a Motzkin word
• Generating words lexicographically: An average-case analysis
• A fast algorithm to generate necklaces with fixed content
• A bijection between ordered trees and 2-Motzkin paths and its many consequences
• The random generation of underdiagonal walks
• Ranking and unranking of a generalized Dyck language and the application to the generation of random trees
• Generating trees and proper Riordan arrays
• Non-uniform random generation of generalized Motzkin paths
• Efficient iteration in admissible combinatorial classes
• A generic approach for the unranking of labeled combinatorial classes
• On Some Alternative Characterizations of Riordan Arrays
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Boltzmann Sampling of Unlabelled Structures
• Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
• Motzkin numbers

This page was built for publication: The relevant prefixes of coloured Motzkin walks: an average case analysis