Permutations realized by shifts
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009)
Cet article a éte moissonné depuis la source Episciences
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.
@article{DMTCS_2009_special_256_a67,
author = {Elizalde, Sergi},
title = {Permutations realized by shifts},
journal = {Discrete mathematics & theoretical computer science},
year = {2009},
volume = {DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)},
doi = {10.46298/dmtcs.2745},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2745/}
}
TY - JOUR AU - Elizalde, Sergi TI - Permutations realized by shifts JO - Discrete mathematics & theoretical computer science PY - 2009 VL - DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) UR - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2745/ DO - 10.46298/dmtcs.2745 LA - en ID - DMTCS_2009_special_256_a67 ER -
%0 Journal Article %A Elizalde, Sergi %T Permutations realized by shifts %J Discrete mathematics & theoretical computer science %D 2009 %V DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) %U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2745/ %R 10.46298/dmtcs.2745 %G en %F DMTCS_2009_special_256_a67
Elizalde, Sergi. Permutations realized by shifts. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009). doi: 10.46298/dmtcs.2745
Cité par Sources :