Donaghey's transformation: carousel effects and tame components | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/2

In this paper, Donaghey's transformation is investigated. It is a combinatorial dynamical system, based on the combinatorial interpretations of Catalan numbers, with the transition function of it being the composition of the direct and the inverse bijections between cubic and non-cubic trees. The dynamical system under investigation operates on a finite set and is inversible; therefore it is a mere permutation of trees. The properties of the cycles of this permutation, called the orbits, are studied in terms of permutation of structural elements of trees. In the course of studies, the systematic initiation of particular effects is indicated. These particular effects are referred to as “carousel”: it is the movement of ob jects from one classification category to another, typical of natural classifications. In this form, they look as an indicator of system complexity. Two new carousel effects for structural elements, referred to as triads and germs, are described. The carousel effect for triads is used for the detection of two families of trees; the lengths of all tree arcs in the first family are equal to one; in the second family, they are equal to two. Here, the term “the arcs of the orbit” is used to denote its fragments between two trees, which have no left subtrees. Therefore, the properties of the arcs are the global properties of the orbits, and the carousel effects are local. The corresponding enumeration problems are solved: it is demonstrated C 5n that the number of trees of the first family increases as I --r,----z-t:;---- | , n3/2 24/3 - 22/3 + 1 3n+1 /2 the number of trees of the second family - as i.-, r- (n is the number of triads). n;3// П . The paper presents the family of cycles with the length 6, which are different from the ones discovered by L. Shapiro, the number of which increases as 0(n2), and the family of cycles with length 9, the number of which increases as 0(2n/2). A class of orbits with the lengths growing up as 0(n2) is detected.
Download file
Counter downloads: 128
  • Title Donaghey's transformation: carousel effects and tame components
  • Headline Donaghey's transformation: carousel effects and tame components
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 44
  • Date:
  • DOI 10.17223/20710410/44/2
Keywords
числа Каталана, плоские кубические деревья, преобразование Донахью, орбиты, карусельный эффект, ручные компоненты, Catalan numbers, plane cubic trees, Donaghey's transformation, carousel effect, tame components
Authors
References
Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. М.: Мир, 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с
 Donaghey's transformation: carousel effects and tame components | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/2
Donaghey's transformation: carousel effects and tame components | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/2
Download full-text version
Counter downloads: 365