## Sergi Elizalde - Permutations realized by shifts

dmtcs:2745 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2745
Permutations realized by shifts

• 1 Department of Mathematics [Dartmouth]

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.

Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: shift,consecutive pattern,forbidden pattern,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
{"ft_lang_label":"__label__en","ft_lang_prob":0.85319805,"math_prob":0.89120555,"size":1107,"snap":"2023-40-2023-50","text_gpt3_token_len":293,"char_repetition_ratio":0.11514053,"word_repetition_ratio":0.03726708,"special_character_ratio":0.26287264,"punctuation_ratio":0.13235295,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98084223,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-21T23:17:57Z\",\"WARC-Record-ID\":\"<urn:uuid:c889ff77-59d2-442c-a506-62b695a8f8ac>\",\"Content-Length\":\"48333\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d7dd2eeb-a38a-4129-8134-186003d77a5c>\",\"WARC-Concurrent-To\":\"<urn:uuid:726a5983-b061-4bc5-989b-a5f036d4f879>\",\"WARC-IP-Address\":\"193.48.96.94\",\"WARC-Target-URI\":\"https://dmtcs.episciences.org/2745\",\"WARC-Payload-Digest\":\"sha1:TM7VDHGUMEOPYQSRFNGCO35G34BW4NYZ\",\"WARC-Block-Digest\":\"sha1:IXAQOUYVJB66PZHDSORKTRCO2SX4YYFP\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233506045.12_warc_CC-MAIN-20230921210007-20230922000007-00837.warc.gz\"}"}