árboles con ary$n$ - - nodos internos -$k$ los números de Catalan

Question

Se sabe que el catalán números de contar el número de árboles binarios con $k$-nodos internos. Yo estaba pensando en cómo contar el ternario de los árboles o en general $n$-ary árboles con $k$ nodos internos, y obtuvo la siguiente recurrencia:

$F_{k+1}=\sum_{a_1+a_2+\ldots+a_n=k} F_{a_1} F_{a_2} \ldots F_{a_n}$

Donde $F_k$ es el número de $n$-ary árboles con $k$ nodos internos.

Así que traté de escribir una generación de función para esta recurrencia. Si $f(x)$ representa la generación de la función he descubierto que $f(x)$ satisface la siguiente ecuación funcional:

$x[f(x)]^n-f(x)+1=0$

Estoy bastante seguro de que este es uno de los "niza" polinomios que tiene una escuela primaria de la solución, incluso cuando $n \geq 5$. El problema es que se pone desagradable, por así decirlo, incluso para $n=3$. Por lo tanto estoy buscando una combinatoria solución: tal vez un $n$D red y el uso de coeficientes multinomiales?

Answer 1

Tal vez ya han encontrado una mejor respuesta, pero aquí es mío si puede ayudar. Puede utilizar la fórmula de inversión de Lagrange-Bürmann. Usted encontrará que su$f(X)$ puede ser expresado tiene una serie de Taylor con el coeficiente de$x^m$ siendo el generalizado$n$ - ésimo número catalán y luego, si no me equivoco el$F(k)$ debiera ser:

$F(k) = \frac{1}{(n-1)k + 1}{nk \choose k}$

Se refiere a Gianfranco OLDANI

Answer 2

Número de$k$ - árboles ario ( «alboroto-Catalán número») es igual al número de trayectorias de celosía que nunca pasan por encima de la diagonale de$n\times nk$ rectángulo.

Como es habitual, este número puede ser calculada utilizando un (variación de) principio de reflexión (véase, por ejemplo M. Renault perdida (y encontrado) en Traducción:. Método Actual de Andre y su aplicación al problema generalizado Ballot ).

Answer 3

Catalán número $C_n$ es también igual al número de formas de horquillado n-veces no cummutative, no asociativo multiplicaciones.
$(a\cdot b)\cdot c$ , por ejemplo, es diferente de $a\cdot(b\cdot c)$
Está claro que $C_1 = 1, C_2 = 1$.

Ahora observe que para una expresión como $(a\cdot b\cdot c)\cdot (d\cdot e\cdot f \cdot g)$, la última multiplicación siempre sucede entre los dos bloques, y cada bloque tiene diferentes formas de horquillado en el interior. En este ejemplo, el bloque de izquierda ha $C_3$ formas de horquillado y el bloque de la derecha ha $C_4$ formas de horquillado. $$C_n = \sum_{k = 1}^{n-1}C_kC_{n-k}$$

Esto se ve como la convolución de dos series llamadas y el mal para la multiplicación de generación de función.
$$g(z): = \sum_{n = 1}^\infty C_n z^n$$ $$g(z)g(z) = (\sum_{n = 1}^\infty C_n z^n)(\sum_{n = 1}^\infty C_n z^n) = \sum_{n = 1}^\infty(\sum_{k = 1}^{n-1}C_k C_{n-k})= \sum_{n = 2}^\infty C_nz^n = g(z)-z$$ Cedemos $$g(z)^2-g(z)+z = 0$$ El uso hecho de que $$f(x) = (1+x)^{1/2}= \sum_{k = 0}^\infty \frac{1}{k!}f^{(k)}(0)x^k = \sum_{k = 0}^\infty a_n x^k$$ donde $$a_n = \binom{\frac{1}{2}}{n} = \frac{(-1)^{k-1}(2k-2)!}{2^{2k-1}k!(k-1)!}$$ Ahora $$g(z) = \frac{1\pm \sqrt{1-4z}}{2} = \frac{1}{2}(1\pm\sqrt{1-4z})$$ Ya sabemos $C_n \ge 0$ $$ g(z) = \frac{1}{2}\sum_{n = 1}^\infty (-a_n)(-4z)^n = \frac{1}{2}\sum_{n = 1}^\infty (-1)(-1)\binom{2n-2}{2n-1}\frac{2}{n} = \sum_{n = 1}^\infty \binom{2n-2}{2n-1}\frac{1}{n}$$ $$\Longrightarrow C_n = \binom{2n-2}{n-1}\frac{1}{n}$$