Interpretación combinatoria de los coeficientes de reversión de la serie

Question

En un reciente papel estudiando algunas generalizaciones de los números de Stirling, mis coautores y yo necesitábamos el siguiente resultado:

Si $f(x)=\sum_{n \geq 1} a_n x^n/n!$ es una serie de potencias con $a_1 \neq 0$ y $g(x) = \sum_{n \geq 1} b_n x^n/n!$ es su reversión en serie (por lo que $f(g(x))=g(f(x))=x$ ), entonces $$ b_n = \sum_{T} w(T) $$
donde la suma es sobre los árboles filogenéticos en $\{1, \ldots, n\}$ . Aquí un árbol filogenético en $\{1,\ldots, n\}$ es un árbol rooteado con $n$ hojas, ningún vértice con exactamente un hijo, y hojas etiquetadas del conjunto $\{1, \ldots, n\}$ (pero ningún otro vértice que reciba una etiqueta); véase la página 3 del documento enlazado anteriormente para ver una imagen. El peso $w(T)$ se calcula como sigue: si $T$ tiene $n$ hojas y $m$ no deja entonces $$ w(T) = (−1)^m a_1^{-(m+n)} \prod \{a_{d(v)}: v~\mbox{a non-leaf}\} $$ donde $d(v)$ denota el número de hijos de $v$ (y cuando $n=1$ el vértice aislado se considera una hoja).

La prueba es corta, y esto parece algo que debería haber sido escrito antes de ahora, pero no pudimos encontrar ninguna referencia.

Pregunta : ¿Ha aparecido el resultado anterior en la literatura?

(Hay un papel de Chen de 1990 con un resultado similar pero con una formulación claramente diferente y no obviamente equivalente. Chen muestra que $b_n$ es una suma ponderada sobre Árboles de Schroeder : árboles en $n$ etiquetado vértices (a diferencia de las hojas), sin restricción de número de hijos, en los que cada no-hoja está dotada de una partición ordenada de sus hijos. El número de árboles de Schroeder por número de vértices es A053492 . El recuento de árboles filogenéticos por número de hojas es A000311 .)

Answer 1

Sí, esto se sabe. Como mencionó Tom Copeland, esto está en La tesis de Drake Ejemplo 1.4.7.

Drake da una amplia generalización de su resultado. Su teorema principal (Teorema 1.3.3) es aproximadamente el siguiente. Suponga que tiene un alfabeto $A$ de ciertos árboles, y un conjunto $L$ de "enlaces permitidos" entre ellos, formas de conectar la raíz de uno con una hoja de otro. Sea $S(L,n)$ sea el conjunto de todos los árboles $T$ con $n$ hojas etiquetadas bijetivamente $1, \ldots, n$ sin otros nodos etiquetados con la propiedad que $T$ formado por las letras $A$ con sólo vínculos entre ellos que se encuentran en $L$ . Digamos que cada árbol $T \in A$ tiene un peso $w(T)$ y un árbol formado por letras $T_1, \ldots, T_n \in A$ con ciertos vínculos entre ellos tiene peso $w(T_1) \cdots w(T_n)$ . Sea $$F(x) = \sum_{n=1}^\infty a_n \frac{x^n}{n!}$$ donde $a_n = \sum_{T \in S(L,n)} w(T)$ . Entonces la inversa composicional es $$F^{-1}(x) = \sum_{n=1}^\infty b_n \frac{x^n}{n!}$$ donde $$b_n = \sum_{T \in S(\bar{L},n)} (-1)^{m(T)} w(T).$$ Aquí $m(T)$ es el número de letras en $A$ que $T$ se compone de, y $\bar{L}$ es el complemento de $L$ en el conjunto de todos los posibles enlaces entre elementos de $A$ .

Se trata de una extensión del trabajo de Susan Parker, que tenía un teorema similar utilizando funciones generadoras ordinarias. El resultado de Parker puede considerarse, a su vez, una generalización de un resultado de Carlitz, Scoville y Vaughan. El resultado de Ira Gessel diapositivas puede ser útil.

Para obtener su teorema, dejemos $A$ sea el conjunto de árboles "simples", los árboles $T_n$ , $n > 1$ para que $T_n$ es un árbol cuya raíz tiene el $n$ deja $1,2, \ldots, n$ como niños. Deja que $w(T_n) = t_n$ (un indeterminado). Sea $L$ sea el conjunto vacío de enlaces. Entonces $$F(x) = x + t_2\frac{x^2}{2!} + t_3 \frac{x^3}{3!} + \cdots$$ desde $S(L,n) = \{T_n\}$ para $n>1$ y $S(L,1)$ consiste en el árbol con un nodo que siempre está permitido (y tiene peso $1$ ).

Entonces, por el teorema de inversión de Drake, $$F^{-1}(x) = \sum_{n=1}^\infty b_n \frac{x^n}{n!}$$ donde $$b_n = \sum_{T \in S(\bar{L},n)} (-1)^{m(T)} w(T)$$ es la suma de los pesos de todo árboles filogenéticos (ya que $\bar{L}$ es el conjunto de todos los enlaces).

Ver también mi tesis que contiene una generalización diferente de su resultado. Los árboles filogenéticos (también llamados particiones totales) se mencionan en la sección 3.2

Answer 2

Véanse estos tres documentos y sus referencias:

https://arxiv.org/abs/math/0208174

https://arxiv.org/abs/math/0208173

http://www.emis.de/journals/SLC/wpapers/s49abdess.html

Pasar de un tipo de árbol a otro no es gran cosa en el marco de la teoría de las especies combinatorias de Joyal. Los tipos de árboles corresponden a ciertos funtores entre conjuntos finitos y para cada uno de esos funtores hay una serie generadora exponencial asociada. El cambio de, por ejemplo, árboles planares a árboles de Cayley es un morfismo de funtores y existe un teorema preciso que dice lo que ocurre entonces con la serie generadora (el teorema 8 del último artículo que he enumerado).