Skip to Main content Skip to Navigation
Conference papers

Permutations realized by shifts

Abstract : 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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:09:47 AM
Last modification on : Wednesday, June 26, 2019 - 4:36:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:57:13 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01185438, version 1



Sergi Elizalde. Permutations realized by shifts. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.361-372. ⟨hal-01185438⟩



Record views


Files downloads