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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [7 references]

https://hal.inria.fr/hal-01185438
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

File

dmAK0130.pdf
Publisher files allowed on an open archive

Identifiers

• HAL Id : hal-01185438, version 1

Citation

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