Recuento $k$-ary con árboles

Question

El (completo) de numeración binario árbol de problemas da el número de árboles binarios se pueden formar usando $N$ nodos $T(n)= C_n$ donde $C_i$ son los números de catalán. La recursividad forma es $T_n = \sum_{i=0}^{n-1}T_iT_{n-1-i}$. Ahora quiero generalizar la cuenta binaria árbol por:

1. Etiqueta el nodo, de modo que el orden de los asuntos. Esto parece bastante simple, el número de árboles que ahora es $T_n = n!C_n$. La recursividad forma es $n\sum_{i=0}^{n-1}{{n-1\choose i}T_iT_{n-1-i}}$

2. $k$-ary árbol: en lugar de binario, ahora es $k$-ary (y, por supuesto, con nodos etiquetados). No sé si hay un nombre para este problema, pero me parece que no puede encontrar un "buen" recursividad forma o cerrado fórmula para $T_n$.

La pregunta es, pues, preguntando por la recurrencia de la forma (y la forma cerrada si es posible) de la $k$-ary etiquetados árboles problema anterior.

---

¿Qué acerca de una versión más simple de contar ternario árboles (sin etiqueta) ? La recurrencia de la forma es fácil de conseguir, pero ¿qué acerca de la forma cerrada de la misma ?

Answer 1

El número de raíces, ordenado, incompleta, sin etiquetar $k$-ary árboles con $n$ vértices está dada por

$$C^{(k)}_n=\frac1{(k-1)n+1}\binom{kn}n\;.$$

Estos son a veces llamados Alboroto-catalán números; véase Concreto de las Matemáticas (p. 347) y MathWorld (que da dos referencias). Su generación de función $C^{(k)}(x)=\sum_0^\infty C^{(k)}_nx^n$ satisface $C^{(k)}(x)=1+xC^{(k)}(x)^k$. El número de raíces, ordenado, incompleta, sin etiquetar ternario ($k=3$), el cuarto grado ($k=4$), qunitic ($k=5$), sextic ($k=6$), heptic ($k=7$) y octic ($k=8$) de árboles de forma OEIS secuencias A001764, A002293, A002294, A002295, A002296 y A007556, respectivamente. Para obtener el número de la etiqueta de los árboles, sólo se debe multiplicar por $n!$.

Answer 2

Vale la pena señalar que podemos derivar la forma cerrada de la expresión que hace referencia @joriki de Hormigón Matemáticas usando una variante de Lagrange de la inversión. Supongamos que la ecuación funcional de estos árboles es $$T(z) = 1 + z\times T(z)^k.$$ Re-escribo esto como (poner $w=T(z)$) $$z = \frac{w-1}{w^k}$$ y observar que $$dz = \left(\frac{1-k}{w^k} + \frac{k}{w^{k+1}}\right) dw.$$ Siguiendo el procedimiento dado en Wilf del generatingfunctionology (2ª ed. sección 5.1 LIF) buscamos para calcular $$[z^n] T(z) = \frac{1}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz$$ que mediante la sustitución anterior se convierte en $$\frac{1}{2\pi i}\int_{|w-1|=\epsilon} \frac{w^{k(n+1)}}{(w-1)^{n+1}} \times w \times \left( \frac{1-k}{w^k} + \frac{k}{w^{k+1}} \right) dw.$$ Este es $$\frac{1}{2\pi i}\int_{|w-1|=\epsilon} \left((1-k) \frac{w^{kn+1}}{(w-1)^{n+1}} + k \frac{w^{kn}}{(w-1)^{n+1}}\right)dw.$$ Ahora expandir los dos términos, llegar $$w^{kn+1} = \sum_{q=0}^{kn+1} {kn+1\elegir q} (w-1)^q \quad\text{y}\quad w^{kn} = \sum_{q=0}^{kn} {kn\elegir q} (w-1)^q.$$ Extraer el plazo para $q=n$ de estas cantidades obtenemos $$(1-k) {kn+1\choose n} + k {kn\choose n}.$$ Este es $$(1-k) \frac{kn+1}{(k-1)n+1} {kn\choose n} + k {kn\choose n}$$ que es $$\frac{1}{(k-1)n+1} {kn\choose n}.$$

Answer 3

Ampliación de Marko Riedl la respuesta, queremos resolver la serie de $T(z)$ donde: $$ T(z) = 1 + z T(z)^k $$ Cambio de variables a $u \mapsto T(z) - 1$ por lo que: $$ u = z (u + 1)^k $$ El Bürmann-Lagrange de la inversión de la fórmula para $u = z \phi(u)$ da $$ [z^n] u(z) = \frac{1}{n} [u^{n - 1}] \phi^n (u) $$ En nuestro caso: \begin{align} [z^n] u(z) &= \frac{1}{n} [u^{n - 1}] (u + 1)^{k n} \\ &= \frac{1}{n} \binom{k n}{n - 1} \end{align} Esto es válido para $n > 0$. Pero: $$ \frac{1}{n} \binom{n}{n - 1} = \frac{(k n)!}{n (n - 1)! (k - n + 1)!} = \frac{1}{n (k - 1) + 1} \binom{n}{n} $$ Por feliz coincidencia, esto le da el valor correcto 1 para $n = 0$. Y para $k = 2$ da el familiar catalana números.