Número medio de hojas distinguidas en un árbol binario

Question

Por un árbol binario En esta pregunta me refiero a un árbol binario con raíz completa en el que se etiquetan el hijo izquierdo y el derecho. Una hoja de dicho árbol es un vértice de grado como máximo 1 (la mayoría de las referencias probablemente considerarían que una hoja es un vértice de grado exactamente 1) y un vértice interno es un vértice de grado como mínimo 2. Con estas convenciones, hay $C_n=\frac{1}{n+1}$$ {2n} \choose {n} $ binary trees with $ n \in\mathbb N $ internal vertices (and $ n+1 $ leaves). We say that a leaf $ x $ of a binary tree $ T$ es distinguido si $\sigma(x)$ es igual a $x$ para todos los automorfismos del gráfico $\sigma\in\operatorname{Aut}(T)$ .

Por ejemplo, el único árbol binario con 0 vértices internos tiene 1 hoja distinguida, el único árbol binario con 1 vértice interno no tiene ninguna hoja distinguida, los 2 árboles binarios con 2 vértices internos tienen cada uno 1 hoja distinguida, los 5 árboles binarios con 3 vértices internos tienen de media $2/5$ hojas distinguidas y los 14 árboles binarios con 4 vértices internos tienen en promedio $15/7$ hojas distinguidas. Entre estos 14 árboles binarios, 8 tienen 3 hojas distinguidas y 6 tienen una única hoja distinguida.

¿Existe una fórmula conocida o una expansión asintótica del número de hojas distinguidas como $n$ va a $+\infty$ ? ¿Existe una forma de estimar la proporción de árboles binarios con $n+1$ hojas que tienen como máximo (o equivalentemente, como mínimo) $d$ ¿Hojas distinguidas?

La motivación de esta pregunta, y sus tal vez sorprendentes etiquetas, proviene de la sintaxis. Una posible formalización de la sintaxis de las lenguas naturales (comúnmente asociada a los nombres de N.Chomsky y R.Kayne) consiste en suponer que las oraciones se construyen mediante aplicaciones recursivas de una operación binaria que opera sobre un conjunto que contiene (pero no se limita a) elementos léxicos. El proceso da como resultado un árbol binario con algunas hojas unidas a elementos léxicos que se cree que se transforman en una cadena lineal de morfemas. Se cree que para que dicho árbol sea linealizado, tiene que satisfacer una condición que se acerca (aunque en realidad no es equivalente) a la condición de tener elementos léxicos sólo en hojas distinguidas. Uno de los objetivos de la pregunta es hacerse una idea del tamaño relativo del hipotético árbol binario subyacente en comparación con el tamaño de la frase medido de la forma habitual.

Answer 1

Un enfoque de función generadora da una fórmula exacta (extraer la asintótica es algo más tedioso): Sea $d_{n,k}$ denotan el número de árboles binarios con $n$ hojas interiores y $k$ vértices distinguidos. Consideramos los polinomios $D_n=\sum_{k=0}^{n+1}d_{n,k}t^k\in\mathbb N[t]$ . Tenemos $D_0=t$ y la fórmula de recursión $$D_{n+1}(t)=\sum_{k=0}^n D_k(t)D_{n-k}(t)+\mod(n,2)\left((D_{n/2}(1))-(D_{n/2}(t^2))\right)$$ donde $\mod(n,2)\in\{0,1\}$ es $1$ para incluso $n$ y $0$ de lo contrario. (Explicación: El subárbol izquierdo y el derecho por encima de la raíz no son isomórficos y sus hojas distinguidas siguen siendo distinguidas o son isomórficos y todas sus hojas se convierten en no distinguidas. El último caso sólo se da para un número impar $2n+1$ de las hojas interiores y este caso es manejado por el $\mod(n,2)$ corrección).

Los polinomios $D_n$ son impar para $n$ incluso y hasta para $n$ impar y tienen aparentemente todos los ceros en el eje imaginario.

Por supuesto, tenemos $D_n(1)={2n\choose n}/(n+1)$ y $E_n=\frac{D_n'(1)}{D_n(1)}$ da el número medio de hojas distinguidas. Los cocientes $E_n/n$ converge a $\sim .495$ . Asintóticamente, algo menos de la mitad de las hojas se distinguen en un gran árbol aleatorio binario.

Aquí una prueba (no completamente rigurosa) de convergencia para $E_n/n$ : La principal contribución a $E_n$ proviene de árboles bastante desequilibrados que tienen relativamente pocos vértices en uno de los dos subárboles (emitidos desde el vértice raíz). Esto se debe a la asintótica $c_n=\lambda 4^n/n^{3/2}$ . Este tiene un efecto suavizador en el comportamiento de $E_n/n$ (la contribución relativa logarítmicamente pequeña del subárbol pequeño más irregular es asintóticamente idéntica y, por lo tanto, también se regulariza). La corrección puede despreciarse ya que se hace exponencialmente pequeña.

Answer 2

Comenzar con el corregido versión de la fórmula de Roland. (En realidad, ahora creo que tanto él como yo teníamos fórmulas correctas, sólo que mi $n$ es el número de hojas y su es el número de vértices internos. Pero esto lo resolví con el mío, así que no lo reescribiré).

$$D_n(t) = \sum_{k=1}^{n-1} D_k(t) D_{n-k}(t) + [ n \equiv 0 \bmod 2 ] (D_{n/2}(1) - D_{n/2}(t^2)) \quad D_1=t.$$ La selección de $D_0$ es arbitraria ya que nunca entra en la recursión.

Poner $$F(x,t) = \sum_{n=1}^{\infty} D_n(t) x^n.$$ Entonces $$F(x,t) = t x + F(x,t)^2 + F(x^2,1) - F(x^2, t^2).$$ Además, sabemos que $F(x,1)$ es la función generadora catalana $C(x) := (1-\sqrt{1-4x})/2$ . Escribir los primos de la derivada con respecto a $t$ tenemos $$F'(x,1) = x + 2 F'(x,1) F(x,1) - 2 F'(x^2,1).$$

Poniendo $G(x) = F'(x,1)$ tenemos $$G(x) = x + 2 G(x) C(x) - 2 G(x^2)$$ o $$G(x) = \frac{x - 2 G(x^2) }{1-2 C(x)}= \frac{x-2G(x^2)}{\sqrt{1-4x}}.$$ Si se introduce esta fórmula en sí misma, $$G(x) = \frac{x}{\sqrt{1-4x}}- \frac{2 x^2}{\sqrt{(1-4x)(1-4 x^2)}} + \frac{4 x^4}{\sqrt{(1-4x)(1-4x^2)(1-4 x^4)}} - \cdots.$$

Como $x \to 1/4^{-}$ el producto $G(x) \sqrt{1-4x}$ se acerca a $$\frac{1}{4} - \frac{2}{4^2 \sqrt{1-4/4^2}} + \frac{4}{4^4 \sqrt{(1-4/4^2)(1-4/4^4)}} - \frac{8}{4^8 \sqrt{(1-4/4^2)(1-4/4^4)(1-4/4^8)}} + \cdots$$ Llama a esta suma $\beta$ . Dudo que tenga una forma cerrada, pero converge muy rápidamente a $\approx 0.1238$ . De hecho, la suma es alterna, por lo que podemos acotarla entre sumas parciales consecutivas: pasando a $3$ y $4$ términos da $0.123847$ y $0.123776$ si no he cometido ningún error al teclearlo.

Así que $$G(x) \approx \frac{\beta}{\sqrt{1-4x}} \ \mbox{as} \ x \to 1/4^{-}.$$

Mientras tanto, $$x \frac{dC}{dx} = \frac{x}{\sqrt{1-4x}} \approx \frac{1/4}{\sqrt{1-4x}} \ \mbox{as} \ x \to 1/4^{-}.$$

Se quiere calcular la relación del coeficiente de $x^n$ en $G(x)$ y en $x \frac{d C}{d x}$ . Esto sugiere (y los métodos de libros como el de Wilf Generación de funcionalidades debería ser capaz de hacer esto riguroso) que el límite es $4 \beta$ .