¿Existe alguna estructura algebraica en las palabras Dyck de longitud $2n$ o árboles binarios completos de $n+1$ ¿Hojas?

Question

Sólo por curiosidad, me pregunto si hay investigaciones sobre estructuras algebraicas en Palabras de Dyck de longitud $2n$ o (equivalentemente) árboles binarios completos de $n+1$ deja (con $n \in \mathbb{Z}^+$ ).

De hecho, esos dos conjuntos tienen el mismo número de elementos: el $n^{th}$ Número catalán $C_n$ .

He buscado en Google pero no he obtenido ningún resultado.

Gracias de antemano.

Answer 1

De hecho, existe una enorme bibliografía sobre este tema. Véase el capítulo 11, Palabras y árboles, en [2] y el lema 9.3.1 en [4] para tu pregunta concreta. Vea las notas del Capítulo 9 en [3] para (muchas) referencias relevantes. La referencia [3] no aborda tu pregunta pero sigue siendo una buena referencia sobre álgebra sobre palabras. Para una teoría algebraica de lenguajes libres de contexto, véase [2] y el capítulo 2 de [1].

[1] Berstel, Jean. Transducciones y lenguajes libres de contexto . Guías de Matemática y Mecánica Aplicadas, 38 B. G. Teubner, Stuttgart, 1979. 278 pp. ISBN: 3-519-02340-7

[1] Berstel, J.; Boasson, L. Hacia una teoría algebraica de los lenguajes libres de contexto Fondo. Inform. 25 (1996), no. 3-4, 217--239

[2] Lothaire, M. Combinatoria de palabras. Con prólogo de Roger Lyndon y prefacio de Dominique Perrin. Reimpresión corregida del original de 1983, con un nuevo prefacio de Perrin. Biblioteca Matemática de Cambridge. Cambridge University Press, Cambridge, 1997. xviii+238 pp. ISBN: 0-521-59924-5

[3] Lothaire, M. Combinatoria algebraica de palabras. Una obra colectiva de Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki y Wojciech Plandowski. Con prefacio de Berstel y Perrin. Encyclopedia of Mathematics and its Applications, 90. Cambridge University Press, Cambridge, 2002. Cambridge University Press, Cambridge, 2002. xiv+504 pp. ISBN: 0-521-81220-8 MR1905123

[4] Lothaire, M. Combinatoria aplicada a las palabras . Obra colectiva de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé. Con prefacio de Berstel y Perrin. Encyclopedia of Mathematics and its Applications, 105. Cambridge University Press, Cambridge, 2005. Cambridge University Press, Cambridge, 2005. xvi+610 pp. ISBN: 978-0-521-84802-2; 0-521-84802-4