Three Lengths Pattern Avoiding Permutation and the Catalan Numbers

Abstract

Let lisj be the set (I, 2, ..., of and let Sy, the set ofall permutations ofPd. Two sequences rand a of length k are of the same type ON < a(i < for all i s i, j sk or equivalently rand a have the mane pair wise comparison throughout. We say that Si, avoids a permutation r provided x has no subsequence of type r for all r< e S . We denote Sit) for such set of r-avoiding permsamions and /S (1) / denotes its cardinality. The permutation in that role, is frequently called as pattern. The problem of pattern (or patterns) avoiding permutation has proved to be useful language in a variety of seemingly unrelated problems, front theory of !Ca:Arian-Lie:sag polynomials, to singularities of Schubert varieties, to Chelossisev polynorniak, to roolcpolynonsials for a rectangular board to various sorting algorithms, sorting stacks and sortable permutations. From some researches of this field a number of emanerative results have been proved new bijections found and connections to otherfields established This paper will focus to all three lengths single pattern. There are six permutations of131. By reversal and complement bijection of a permutation, the six permutations can be reduced into two classes, where 132 and 123 are in two raiment classes. Furthermore, by concept of left-to-right minima we found that there is bijection between S (123) and S (132). Finally, we shown that IS (132) 1 is Catalan nwnber.