Перечислительные задачи, связанные с преобразованием Донахью

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

плоские деревья, примитивные деревья, преобразование Донахью, производящие функции, дуги преобразования, графы поворотов

1. R. Donaghey, “Automorphisms on Catalan trees and bracketings”, Journal of Combinatorial Theory, 29:1 (1980), 75-90.

2. L. W. Shapiro, “The cycle of six”, The Fibonacci Quarterly, 17:3 (1979), 253-259.

3. D. Callan, “A bijection on Dyck paths and its cycle structure”, The Electronic Journal of Combinatorics, 14:1 (2007), R28.

4. A. Karttunen, URL: http://www.oeis.org/A080070.

5. D. E. Knuth, The Art of Computer Programming, Part 1. V. 4A: Combinatorial Algorithms, Addison-Wesley Professional, New Jersey, 2011.

6. F. Bergeron, G. Labelle, P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, New York, 1997.

7. И. А. Пушкарев, В. А. Бызов, “Дуги преобразования Донахью и треугольник Каталана”, Научно-технический вестник Поволжья, 2015, №1, 19-22.

8. R. Donaghey, “Restricted plane tree representations of four Motzkin-Catalan equations”, Journal of Combinatorial Theory. Series B, 22:2 (1977), 114-121.

9. R. Donaghey, L. W. Shapiro, “Motzkin numbers”, Journal of Combinatorial Theory. Series A, 23:3 (1977), 291-301.

10. F. R. Bernhart, “Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics, 204:1-3 (1999), 73-112.

11. M. Drmota, “A bivariate asymptotic expansion of coefficients of powers of generating functions”, European Journal of Combinatorics, 15:2 (1994), 139-152.

12. M. H. Albert, V. Vatter, “Generating and enumerating 321-avoiding and skew-merged simple permutations”, Electronic Journal of Combinatorics, 20:2 (2013), P44.

13. M. Dairyko, L. Pudwell, S. Tyner, C. Wynn, “Non-contiguous pattern avoidance in binary trees”, Electronic Journal of Combinatorics, 19:3 (2012), P22.

14. 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/.