dmtcs:2745 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2009,
DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)

https://doi.org/10.46298/dmtcs.2745
Permutations realized by shifts
Authors: Sergi Elizalde ^{1}
0000000341162455
Sergi Elizalde
1 Department of Mathematics [Dartmouth]
A permutation $\pi$ 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 $\pi$. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [J.M. Amigó, S. Elizalde and M. Kennel, $\textit{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 with respect to their length.