Russian Universities Reports. MathematicsRussian Universities Reports. MathematicsВестник российских университетов. Математика2686-96672782-3342Tambov State University - G.R. Derzhavin29729710.20310/1810-0198-2019-24-125-5-25ArticlesСтатьиResearch ArticleEnumeration problems associated with Donaghey’s transformationПеречислительные задачи, связанные с преобразованием ДонахьюByzovViktor A.БызовВиктор Александрович

Senior Lecturer of the Applied Mathematics and Informatics Department

старший преподаватель кафедры прикладной математики и информатики

vbyzov@yandex.ruVyatka State UniversityФГБОУ ВО «Вятский государственный университет»1512201924125VOL 24, NO125 (2019)ТОМ 24, №125 (2019)52520062025Copyright ©; 2025, Byzov V.A.Copyright ©; 2025, Бызов В.А.2025Byzov V.A.Бызов В.А.https://creativecommons.org/licenses/by/4.0https://journals.rcsi.science/2686-9667/article/view/297297

In this paper we consider enumeration problems associated with Donaghey’s transformation. We discuss two groups of questions. The first one is related to the enumeration of fragments of transformation orbits, which are referred to as the “arcs”. The second group of questions is concerned with finding the number of vertices in rotation graphs-a specific family of graphs that is by nature an approximation of Donaghey’s transformation. The basic results of this work are formulated in the form of generating functions and corresponding asymptotics.

Работа посвящена рассмотрению перечислительных задач, связанных с преобразованием Донахью. Обсуждаются две группы вопросов. Первая группа связана с перечислением фрагментов орбит преобразования, называемых «дугами». Вторая часть работы посвящена нахождению количества вершин в графах поворотов-специфическом семействе графов, представляющем собой «аппроксимацию» преобразования Донахью. Основные результаты данной работы сформулированы в виде производящихфункций и соответствующих асимптотик.

plane treesprimitive treesDonaghey’s transformationgenerating functionsarcs of transformationgraphs of rotationsплоские деревьяпримитивные деревьяпреобразование Донахьюпроизводящие функциидуги преобразованияграфы поворотовR. Donaghey, “Automorphisms on Catalan trees and bracketings”, Journal of Combinatorial Theory, 29:1 (1980), 75-90.L. W. Shapiro, “The cycle of six”, The Fibonacci Quarterly, 17:3 (1979), 253-259.D. Callan, “A bijection on Dyck paths and its cycle structure”, The Electronic Journal of Combinatorics, 14:1 (2007), R28.A. Karttunen, URL: http://www.oeis.org/A080070.D. E. Knuth, The Art of Computer Programming, Part 1. V. 4A: Combinatorial Algorithms, Addison-Wesley Professional, New Jersey, 2011.F. Bergeron, G. Labelle, P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, New York, 1997.И. А. Пушкарев, В. А. Бызов, “Дуги преобразования Донахью и треугольник Каталана”, Научно-технический вестник Поволжья, 2015, №1, 19-22.R. Donaghey, “Restricted plane tree representations of four Motzkin-Catalan equations”, Journal of Combinatorial Theory. Series B, 22:2 (1977), 114-121.R. Donaghey, L. W. Shapiro, “Motzkin numbers”, Journal of Combinatorial Theory. Series A, 23:3 (1977), 291-301.F. R. Bernhart, “Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics, 204:1-3 (1999), 73-112.M. Drmota, “A bivariate asymptotic expansion of coefficients of powers of generating functions”, European Journal of Combinatorics, 15:2 (1994), 139-152.M. H. Albert, V. Vatter, “Generating and enumerating 321-avoiding and skew-merged simple permutations”, Electronic Journal of Combinatorics, 20:2 (2013), P44.M. Dairyko, L. Pudwell, S. Tyner, C. Wynn, “Non-contiguous pattern avoidance in binary trees”, Electronic Journal of Combinatorics, 19:3 (2012), P22.Q. Yuan, The catalan numbers, regular languages, and orthogonal polynomials, URL: https://qchu.wordpress.com/2009/06/07/the-catalan-numbers-regular-languages-andorthogonal-polynomials/.