The number of permutations realized by a shift

Details The number of permutations realized by a shift The number of permutations realized by a shift

2009-09-11

arxiv.org/abs/0909.2274v1

S. Elizalde, SIAM J. Discrete Math. 23 (2009), 765-786

Mathematics

Combinatorics

19 pages, 2 figures

Scientific paper

10.1137/080726689

A permutation p is realized by the shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as p. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [Amigo, Elizalde, Kennel, J. Combin. Theory Ser. A 115 (2008) 485-504] that the shortest forbidden patterns of the shift on N symbols have length N+2. In this paper we give a characterization of the set of permutations that are realized by the shift on N symbols, and we enumerate them according to their length.

Affiliated with

Also associated with

No associations

Rating

The number of permutations realized by a shift does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The number of permutations realized by a shift, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of permutations realized by a shift will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-477041