RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2012, том 9, страницы 346–359 (Mi semr360)

Дискретная математика и математическая кибернетика

Антимонотонные перестановки

М. А. Макаров

Институт математики им. С. Л. Соболева СО РАН, пр. академика Коптюга 4, 630090, Новосибирск, Россия

Аннотация: 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.

Ключевые слова: infinite permutations, combinatorics on words, Rauzy graphs, maximal pattern complexity, arithmetical complexity.

УДК: 519.1

MSC: 68R05

Поступила 26 мая 2012 г., опубликована 30 июля 2012 г.



© МИАН, 2024