Geodesic
Enumeration problems associated with Donaghey’s transformation
Vestnik rossijskih universitetov. Matematika, Tome 24 (2019) no. 125, pp. 5-25 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: plane trees, primitive trees, Donaghey’s transformation, generating functions, graphs of rotations.
Mots-clés : arcs of transformation 
@article{VTAMU_2019_24_125_a0,
     author = {V. A. Byzov},
     title = {Enumeration problems associated with {Donaghey{\textquoteright}s} transformation},
     journal = {Vestnik rossijskih universitetov. Matematika},
     pages = {5--25},
     year = {2019},
     volume = {24},
     number = {125},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTAMU_2019_24_125_a0/}
}
TY  - JOUR
AU  - V. A. Byzov
TI  - Enumeration problems associated with Donaghey’s transformation
JO  - Vestnik rossijskih universitetov. Matematika
PY  - 2019
SP  - 5
EP  - 25
VL  - 24
IS  - 125
UR  - http://geodesic.mathdoc.fr/item/VTAMU_2019_24_125_a0/
LA  - ru
ID  - VTAMU_2019_24_125_a0
ER  - 
%0 Journal Article
%A V. A. Byzov
%T Enumeration problems associated with Donaghey’s transformation
%J Vestnik rossijskih universitetov. Matematika
%D 2019
%P 5-25
%V 24
%N 125
%U http://geodesic.mathdoc.fr/item/VTAMU_2019_24_125_a0/
%G ru
%F VTAMU_2019_24_125_a0
V. A. Byzov. Enumeration problems associated with Donaghey’s transformation. Vestnik rossijskih universitetov. Matematika, Tome 24 (2019) no. 125, pp. 5-25. http://geodesic.mathdoc.fr/item/VTAMU_2019_24_125_a0/

[1] R. Donaghey, “Automorphisms on Catalan trees and bracketings”, Journal of Combinatorial Theory, 29:1, no. B (1980), 75–90 | DOI | MR | Zbl

[2] L. W. Shapiro, “The cycle of six”, The Fibonacci Quarterly, 17:3 (1979), 253–259 | MR | Zbl

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

[4] A. Karttunen, 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 | MR | Zbl

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

[7] I. A. Pushkarev, V. A. Byzov, “Arcs of Donaghey's Transformation and Catalan's Triangle”, Scientific and Technical Volga Region Bulletin, 2015, no. 1, 19–22 (In Russian)

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

[9] R. Donaghey, L. W. Shapiro, “Motzkin numbers”, Journal of Combinatorial Theory. Series A, 23:3 (1977), 291–301 | DOI | MR | Zbl

[10] F. R. Bernhart, “Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics, 204:1–3 (1999), 73–112 | DOI | MR | Zbl

[11] M. Drmota, “A bivariate asymptotic expansion of coefficients of powers of generating functions”, European Journal of Combinatorics, 15:2 (1994), 139–152 | DOI | MR | Zbl

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

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

[14] Q. Yuan, The catalan numbers, regular languages, and orthogonal polynomials, https://qchu.wordpress.com/2009/06/07/the-catalan-numbers-regular-languages-and-orthogonal-polynomials/