The number of permutations realized by a shift Export

@article{citeulike:5789262, abstract = {A permutation p 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 p. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [Amigo, Elizalde, Kennel, 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 according to their length.}, archivePrefix = {arXiv}, author = {Elizalde, Sergi}, citeulike-article-id = {5789262}, citeulike-linkout-0 = {http://arxiv.org/abs/0909.2274}, citeulike-linkout-1 = {http://arxiv.org/pdf/0909.2274}, citeulike-linkout-2 = {http://dx.doi.org/10.1137/080726689}, day = {11}, doi = {10.1137/080726689}, eprint = {0909.2274}, keywords = {a, by, number, of, permutations, realized, shift}, month = {Sep}, posted-at = {2009-09-15 20:41:33}, priority = {2}, title = {The number of permutations realized by a shift}, url = {http://dx.doi.org/10.1137/080726689}, year = {2009} }

TY - JOUR ID - citeulike:5789262 L3 - citeulike-article-id:5789262 N2 - A permutation p 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 p. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [Amigo, Elizalde, Kennel, 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 according to their length. TI - The number of permutations realized by a shift KW - a KW - by KW - number KW - of KW - permutations KW - realized KW - shift AU - Elizalde, Sergi PY - 2009/Sep/11/ UR - http://dx.doi.org/10.1137/080726689 ER -