Non uniform random generation of generalized Motzkin paths

We consider in this paper the class M_k^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_k^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).