From Motzkin to Catalan permutations

For every integer j greater than or equal to 1, we define a class of permutations in terms of certain forbidden subsequences. For j = 1, the corresponding permutations are counted by the Motzkin numbers, and for j = infinity (defined in the text), they are counted by the Catalan numbers. Each value of j > 1 gives rise to a counting sequence that lies between the Motzkin and the Catalan numbers. We compute the generating function associated to these permutations according to several parameters. For every j greater than or equal to 1, we show that only this generating function is algebraic according to the length of the permutations. (C) 2000 Elsevier Science B.V. All rights reserved.