The Realization Of Permutations In Symbolic Space

Let(x,≤)be a totally ordered set.We denote by Sn the set of bejective of{1,2, n).For any x1,x2,...,xn∈X,pairwise different,there is a permutation π∈Sn such that xπ(1)<xπ(2)<...<xπ(n).Define ρ(x1,x2,...,xn)=(π-1(1),π-1(2),...,π-1(n)). Specially,if x<x2<...<xn,then ρ(x1,x2,...,xn)=(1,2,...,n).Let Q={0,1,...,N-1}N be a symbolic space.Let f:Ω→Ω be the shift operator. With the lexicographic order(<),Ω is a totally ordered set.Let π∈Sn,if there exists some infinite word ω∈Ω such that ρ(ω,f(ω),...,fn-1(ω))=π,we say that π can be realized.The permutations that can be realized are called allowed patterns,the remaining permutations are called forbidden patterns.It is clear that if permutations can be realized on N symbols,it also can be realized on N+1symbols.In this paper,we mainly consider two questions:Firstly,given a permutation π∈Sn,what is the smallest number N such that π can be realized in symbolic space with N symbols.Secondly,we give a detail formula for numbers an,N,which count permutations that can be realized on N symbols but not on N-1symbols.The thesis is organized as follows:in the introductory chapter,we mainly introduce two questions we consider.In the second chapter,we introduce the definitions,notations and propositions.In the third chapter,we present a formula for N(π),which is the smallest number of symbols needed in the alphabet in order for π to be realized by a shift and presents an equivalent characterization.We also give a complete characterization of forbid-den patterns and allowed patterns of shift systems.In the last chapter we first give the ele-ments of Allown(∑2),and then give a detailed formula for numbers an,N by generalizing the two symbols to arbitrary N symbols.Finally,we point out a conject,which has not been proved.