Generating Trees And Restricted Avoiding Alternating Permutations

Pattern avoiding permutations is a subject that is widely been learning by combinatorial mathematics researchist.We mainly study two aspects.Firstly, we discuss the different permutations.For example,the alternating permu-tations we will learn in this paper. Secondly,we learn the different avoiding patterns. We study two aspects in this dissertation,which are restricted al-ternating permutations and consecutive pattern avoiding permutations.A permutation π=π1π1π3…is called an alternating permutation if π1π2>π3…. If π1>π2<π3…,we also call it an alternating permutation. A downup permutation on an ordered set S={s1<s2…<Sn)is one of the form{sil,si2,...sin} with sil>si2<Si3>si4<...An updown permutation is similar but with the inequalities reversed；alternating means downup or updown.We denote the permutation of length n by DUn,UDnAvoiding pattern abc is called consecutive pattern if there is no other elements between a and b andd between b and c.Given two permutations τand u such that u∈Sn(τ).The element m∈[n+1] is called active value for u if u←m avoids τ.This dissertation is organized as follows.In section1.1and1.2,we intro-duce briefly the background of the avoiding permutations,and some terminolo-gies.Section1.3presents the main results and the corresponding results of this paper.In section2.1,we obtain the enumeration formula of the312avoiding alternating permutations.Section2.2is devoted to showing that2134avoiding alternating permutations and2143avoiding alternating permutations have the same generating trees.We get the conclude that|A2n(2134)|=|A2n(2143)|=|SST(n,n,n)|=(2(3n)!)/(n(n+1!(n+2)!) The enumeration formula of consecutive312oiding permutations which is∑k=0「(n-3)/3」Cn-2k-2(k n-2k-2)+∑k=0「(n-1)/3」Cn-2k(k n-2k can be obtaimed in chapter3.