Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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

https://hal.inria.fr/hal-01185438
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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

Collections

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, ⟨10.46298/dmtcs.2745⟩. ⟨hal-01185438⟩

Share

Metrics

Record views

37

Files downloads

399