Non uniform random generation of generalized Motzkin paths

We consider in this paper the class M[sub k][sup n] of generalized Motzkin paths of length n, that is, lattice paths using steps (1,1), (1,-1), (k,0), where k is a fixed positive integer, starting at the origin (0,0), running above the x-axis, and ending at (n,0). The area is the region bounded by t...

Full description

Saved in:
Bibliographic Details
Published in:Acta informatica 2006-04, Vol.42 (8-9), p.603-616
Main Authors: BRLEK, Srecko, PERGOLA, Elisa, ROQUES, Olivier
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Codes
Combinatorics. Ordered structures
Complexity
Computer science
control theory
systems
Exact sciences and technology
Grammar
Integers
Lattices
Mathematics
Order, lattices, ordered algebraic structures
Origins
Rejection
Running
Sciences and techniques of general use
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider in this paper the class M[sub k][sup n] of generalized Motzkin paths of length n, that is, lattice paths using steps (1,1), (1,-1), (k,0), where k is a fixed positive integer, starting at the origin (0,0), running above the x-axis, and ending at (n,0). The area is the region bounded by the path and the x-axis. We first establish a bijection between the area of paths in M[sub k][sup n] and some lattice paths of length n+1. Then, by using a rejection technique, we obtain a linear algorithm with an average time complexity (k mod 2 +1)(n+1). [PUBLICATION ABSTRACT]
ISSN:0001-5903
1432-0525
DOI:10.1007/s00236-006-0008-x