¿Cuántos árboles etiquetados con$n$ de vértices existen de modo que su grado es$1$ o$3$? Logré obtener un rango pero no una respuesta en particular.
EDITAR
el rango que encontré:
ps
Respuesta
¿Demasiados anuncios?
Se presentan dos respuestas, uno con Pruefer códigos y uno el uso de la combinatoria de las especies. Recordemos que el Pruefer código para un árbol en $n$ nodos se muestra una lista de $n-2$ elementos de tomar sus valores de la $n$ nodos, para un total de $n^{n-2}$ árboles. El grado de un nodo en el árbol resultante es uno más que el número de veces que aparece en la lista. Por lo tanto, con los grados uno y tres un nodo aparece no o aparece dos veces. Vemos de inmediato que no hay ningún tipo de los árboles en un número impar de nodos debido a $n-2$ debe ser par.
Ahora, para el cerrado de la fórmula, debemos elegir la $(n-2)/2$ nodos que están presentes en el código y distribuir estos pares en el $n-2$ ranuras. Obtenemos
$${n\elegir (n-2)/2} {n-2\elegir 2,2,\ldots,2} = {n\elegir (n-2)/2} \frac{(n-2)!}{2^{(n-2)/2}}$$
para $n$ aun y cero en caso contrario. Esto da lugar a la secuencia
$$1, 0, 4, 0, 90, 0, 5040, 0, 529200, \\ 0, 89812800, 0, 22475653200,\ldots$$
Para la alternativa de la prueba de introducir la etiqueta de la combinatoria de las especies de árboles de raíces con outdegree dos. Estos tienen total grado tres o de uno en todos los nodos excepto la raíz, que tiene grado dos. La especie la ecuación es
$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\mathfrak{P}_{=2}(\mathcal{T}).$$
De este modo, obtener la ecuación funcional
$$T(z) = z\left(1+\frac{1}{2} T(z)^2\right).$$
Ahora observar que un elemento de la especie objetivo de la $\mathcal{V}$ de sin raíces etiquetado de los árboles con el nodo de grado uno o tres se obtiene por la conexión de dos elementos de $\mathcal{T}$ por un borde entre los dos raíces. De esta manera obtenemos todos los elementos de la $\mathcal{V}$ exactamente $n-1$ veces, por lo que estamos después de que el siguiente coeficiente de
$$\frac{n!}{2(n-1)} [z^n] T(z)^2.$$
Para calcular el valor deseado utilizamos una variante de Lagrange de la inversión. Con $n\ge 2$ hemos
$$\frac{n!}{2(n-1)} [z^n] T(z)^2 = \frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$
Tenemos $$z = \frac{2T(z)}{2+T(z)^2}$$ so putting $T(z) = w$ podemos obtener
$a$z = \frac{2}{2+w^2} \quad\text{y}\quad dz = \left( \frac{2}{2+w^2} - \frac{2}{(2+w^2)^2} 2 \right) dw.$$
Este rendimientos de la integral
$$\frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(2+w^2)^{n+1}}{2^{n+1} w^{n+1}} \frac{2(2-w^2)}{(2+w^2)^2} w^2 \; dw \\ = \frac{n!}{2^{n+1}(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(2+w^2)^{n-1}}{w^{n-1}} (2-w^2) \; ps.$$
Este es claramente el cero al $n-2$ es impar. Al $n$ es incluso podemos obtener
$$\frac{n!}{2^{n+1}(n-1)} [w^{n-2}] (2+w^2)^{n-1} (2-w^2).$$
Ahora, cuando $n=2$ esto se evalúa a
$$\frac{2}{2^3\times 1} \times {1\elegir 0} 2^{n-1} \times 2 = 1$$
cual es el valor correcto. Continuando con $n\ge 4$ obtenemos
$$\frac{n!}{2^{n+1}(n-1)} \left({n-1\elegir (n-2)/2} 2^{n-1-(n-2)/2} \times 2 - {n-1\elegir (n-4)/2} 2^{n-1-(n-4)/2}\right) \\ = n\times(n-2)!\veces \left({n-1\elegir (n-2)/2} 2^{-1-(n-2)/2} - {n-1\elegir (n-4)/2} 2^{-2-(n-4)/2}\right) \\ = \frac{(n-2)!}{2^{n/2}} \times n \times \left({n-1\elegir (n-2)/2} - {n-1\elegir (n-4)/2} \right) \\ = \frac{(n-2)!}{2^{n/2}} \times \left(n {n-1\elegir (n-2)/2} - n \frac{(n-2)/2}{n} {n\elegir (n-2)/2} \right) \\ = \frac{(n-2)!}{2^{n/2}} \times \left((n+2)/2 - (n-2)/2 \right) {n\elegir (n-2)/2} \\ = \frac{(n-2)!}{2^{(n-2)/2}} {n\elegir (n-2)/2}.$$
Este es el reclamo.
Observación. Lagrange de la Inversión es de más maquinaria que tenemos aquí, también podemos usar la fórmula cuadrática para obtener
$$T(z) = \frac{1-\sqrt{1-2z^2}}{z} \quad\text{que}\quad T(z)^2 = \frac{2-2z^2}{z^2} -2\frac{\sqrt{1-2z^2}}{z^2}.$$
Obtenemos $n\ge 2$ $$[z^n] \sqrt{1-2z^2} = {1/2\elegir n/2} (-1)^{n/2} 2^{n/2} \\ = (-1)^{n/2} 2^{n/2} \times \frac{1}{2} \frac{1}{(n/2)!} \prod_{q=0}^{n/2-2} (-1/2-p) = - \frac{1}{(n/2)!} \prod_{q=0}^{(n-4)/2} (1+2t) \\ = - \frac{(n-3)!}{(n/2)!} \frac{1}{2^{(n-4)/2}} \frac{1}{((n-4)/2)!}.$$
A continuación, obtener para $n\ge 4$
$$[z^n]\left(-\frac{2}{z^2}\right) \sqrt{1-2z^2} = -2 [z^{n+2}] \sqrt{1-2z^2} = 2 \frac{(n-1)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!}.$$
La recopilación de todo lo que tenemos finalmente la
$$2 \frac{n!}{2(n-1)} \frac{(n-1)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!} \\= n! \frac{(n-2)!}{((n+2)/2)!} \frac{1}{2^{(n-2)/2}} \frac{1}{((n-2)/2)!} \\ = \frac{(n-2)!}{2^{(n-2)/2}} {n\elegir (n-2)/2}$$
de nuevo como se reivindica.
Adenda. Ahora nos muestran cómo calcular el número de sin raíces la etiqueta de los árboles con el nodo de grado en la mayoría de los tres es decir, incluyendo los nodos de el grado dos. Esto significa que tenemos pares y los únicos presentes en el Pruefer código. Supongamos que tenemos $q$ pares. Debemos elegir estos de la $n$ nodos disponibles y llenar el resto de la Pruefer código con los únicos. Este rendimientos
$$\sum_{q=0}^{\lfloor (n-2)/2\rfloor} {n\elegir q} {n-p\elegir n-2-2t} {n-2\elegir 2,2,\ldots, 1,1,\ldots 1} \\ = \sum_{q=0}^{\lfloor (n-2)/2\rfloor} {n\elegir q} {n-p\elegir n-2-2t} \frac{(n-2)!}{2^{q}}.$$
Hay varias posibilidades para simplificar esto, vamos a utilizar especies. La especie ecuación se convierte ahora en el
$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\mathfrak{P}_{=1}(\mathcal{T}) + \mathcal{Z}\mathfrak{P}_{=2}(\mathcal{T}).$$
De este modo, obtener la ecuación funcional
$$T(z) = z\left(1+ T(z) + \frac{1}{2} T(z)^2\right).$$
La construcción va a través de antes y buscamos
$$\frac{n!}{2(n-1)} [z^n] T(z)^2.$$
Para calcular el valor deseado utilizamos una variante de Lagrange de la inversión. Con $n\ge 2$ hemos
$$\frac{n!}{2(n-1)} [z^n] T(z) = \frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$
Tenemos $$z = \frac{2T(z)}{2+ 2T(z) + T(z)^2}$$ so putting $T(z) = w$ podemos obtener
$a$z = \frac{2}{2+2w+w^2} \quad\text{y}\quad dz = \left( \frac{2}{2+2w+w^2} - \frac{2 \times (2w+2)}{(2+2w+w^2)^2} \right) dw.$$
Este rendimientos de la integral
$$\frac{n!}{2(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(2+2w+w^2)^{n+1}}{2^{n+1} w^{n+1}} \frac{2(2-w^2)}{(2+2w+w^2)^2} w^2 \; dw \\ = \frac{n!}{2^{n+1}(n-1)} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(2+2w+w^2)^{n-1}}{w^{n-1}} (2-w^2) \; ps.$$
Escribimos
$$(2+2w+w^2)^{n-1} = (1+(w+1)^2)^{n-1} = \sum_{q=0}^{n-1} {n-1\elegir q} (w+1)^{t2}$$
Extraer el residuo se obtiene la fórmula
$$\frac{n!}{2^{n+1}(n-1)} \sum_{q=0}^{n-1} {n-1\elegir q} \left(2\times {2t\elegir n-2} - {2t\elegir n-4}\right).$$
Esto da lugar a la secuencia
$$1, 3, 16, 120, 1170, 14070, 201600, 3356640, 63730800, \\ 1359666000, 32212857600, 839350512000, 23860289653200, \\ 734964075846000, \ldots $$
que es OEIS A003692.
Se introduce un coeficiente binomial integral en un esfuerzo para obtener un mejor forma cerrada. Poner
$${n-p\elegir n-2-2t} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1-2t}} (1+v)^{n-q}\; dv.$$
Observar que este se desvanece al$\lfloor(n-2)/2\rfloor \lt q\le n$, por lo que podemos extender el límite superior de la suma a $n,$ la obtención de
$$\frac{(n-2)!}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (1+v)^{n} \sum_{q=0}^n {n\elegir q} \frac{v^{t2}}{2^p(1+v)^p} \; dv \\ = \frac{(n-2)!}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (1+v)^{n} \left(1+\frac{v^2}{2(1+v)}\right)^n \; dv \\ = \frac{(n-2)!}{2^n\times 2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n-1}} (2+2v+v^2)^n\; dv.$$
Extraer el residuo se obtiene una ligera mejoría que produce
$$\frac{(n-2)!}{2^n} \sum_{q=0}^{n} {n\elegir q} {2t\elegir n-2}.$$
