|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2012, Volume 9, Pages 346–359
(Mi semr360)
|
|
|
|
Discrete mathematics and mathematical cybernetics
Antimonotone permutations
M. A. Makarov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
The paper is devoted to a class of infinite permutations. One of the properties of these permutations is their avoiding monotone subsequences of elements with numbers forming an arithmetical progression of length 3. We find the complexity of these permutations, their Rauzy graphs, their maximal pattern complexity, their arithmetical complexity with odd differences, and also we find the lower and upper bounds for their arithmetical complexity and show that these bounds are attained.
Keywords:
infinite permutations, combinatorics on words, Rauzy graphs, maximal pattern complexity, arithmetical complexity.
Received May 26, 2012, published July 30, 2012
Citation:
M. A. Makarov, “Antimonotone permutations”, Sib. Èlektron. Mat. Izv., 9 (2012), 346–359
Linking options:
https://www.mathnet.ru/eng/semr360 https://www.mathnet.ru/eng/semr/v9/p346
|
Statistics & downloads: |
Abstract page: | 204 | Full-text PDF : | 69 | References: | 48 |
|