Pattern avoiding Motzkin paths are almost rational
Submitted
Christian, Antonio, Matteo and Luca
Using a recursive approach, we show that the generating function for sets of Motzkin paths avoiding a single (not necessarily consecutive) pattern is rational over x and the Catalan generating function C(x). Moreover, an algorithm is provided for finding the generating function, also in the more general case of an arbitrary set of patterns. In addition, such an algorithm allows us to find a combinatorial specification for pattern avoiding Motzkin paths, which can be used not only for enumeration, but also for exhaustive and random generation.