ГлавнаяАрхивПреобразование Донахью: карусельные эффекты и ручные компоненты

Преобразование Донахью: карусельные эффекты и ручные компоненты | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/2

Изучается динамическая система, действующая на комбинаторных интерпретациях чисел Каталана. Описаны два новых карусельных эффекта (для триад и ростков), первый из которых использован для перехода от локального свойства деревьев (отсутствие триад определённых типов) к некоторым глобальным свойствам орбит. Показано, что отмеченный эффект носит массовый характер. Построено несколько новых ручных классов орбит, в том числе не только с посто-явными длинами орбит, но и с растущими как &(n2). Решены соответствующие перечислительные задачи.
  • Title Преобразование Донахью: карусельные эффекты и ручные компоненты
  • Headline Преобразование Донахью: карусельные эффекты и ручные компоненты
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 44
  • Date:
  • DOI 10.17223/20710410/44/2
Ключевые слова
числа Каталана, плоские кубические деревья, преобразование Донахью, орбиты, карусельный эффект, ручные компоненты, Catalan numbers, plane cubic trees, Donaghey's transformation, carousel effect, tame components
Авторы
Ссылки
Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. М.: Мир, 2005. 768 с
Татт У. Теория графов. М.: Мир, 1988. 424 с
Пушкарев И. А., Бызов В. А. Преобразование Донахью: элементарный подход // Записки научных семинаров ПОМИ. 2013. Т. 411. С. 148-177
Donaghey R. Automorphisms on Catalan trees and bracketings // J. Combinatorial Theory. Ser. B. 1980. V. 29. No. 1. P. 75-90
Кнут Д. Искусство программирования. Т. 4А. Комбинаторные алгоритмы. Ч. 1. М.: Вильямс, 2016. 960с
Callan D. A bijection on Dyck paths and its cycle structure // Electronic J. Combinatorics. 2007. V.14. No.1. P.R28. www.oeis.org/A080070 - The On-Line Encyclopedia of Integer Sequences. 2003
Пушкарев И. А. Об одном преобразовании плоских деревьев // Математический вестник педвузов и университетов Волго-Вятского региона. 2006. № 8. С. 92-99
Bergeron F., Labelle G., and Leroux P. Combinatorial Species and Tree-like Structures. N.Y.: Cambridge University Press, 1997. 457 p
Shapiro L. W. The cycle of six // The Fibonacci Quarterly. 1979. V. 17. No. 3. P. 253-259
Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703с
Преобразование Донахью: карусельные эффекты и ручные компоненты | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/2
Преобразование Донахью: карусельные эффекты и ручные компоненты | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/2