Me gustaría aportar algunas ideas aunque no tengo mucho
tiempo como me gustaría en este momento. Si entiendo este problema correctamente
luego, la clase de los grafos bajo la consideración de la llamada es $\mathcal{Q}$ es
en un conjunto de relación con la clase de endofunctions llaman
$\mathcal{E}$ con el último de los conjuntos de la primera.
Esto le da a la especie ecuación
$$\mathcal{E} = \mathfrak{P}(\mathcal{Q})$$
que es en términos de generación de funciones
$$E(z) = \exp P(z)
\quad\text{o}\quad
Q(z) = \log E(z).$$
Recordar la popular etiqueta árbol de raíces de la función que representa la
especies
$$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$
y tiene la ecuación funcional
$$T(z) = z \exp T(z).$$
También tenemos que $$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}$$
(La fórmula de Cayley)
y desde allí se $n^n$ endofunctions obtenemos
$$E(z) = 1 + z\frac{d}{dz} T(z) = 1 + z T'(z).$$
Pero a partir de la funcional de la ecuación obtenemos
$$T'(z) = \exp T(z) + z \exp T(z) T'(z) = \frac{T(z)}{z} + T(z) T'(z)$$
así que
$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$
Esto finalmente se rinde
$$E(z) = 1 + \frac{T(z)}{1-T(z)}$$
y, por tanto, $$Q(z) = \log\left(1+\frac{T(z)}{1-T(z)}\right).$$
Esto le da a la secuencia
$$1, 3, 17, 142, 1569, 21576, 355081, 6805296,
\\ 148869153, 3660215680,\ldots$$
que nos señala OEIS A001865
cuando nos enteramos de que, de hecho, tenemos el derecho exponencial de la generación de
la función. Tenga en cuenta que la fórmula para $E(z)$ también demuestra que
$\mathcal{E} = \mathfrak{S}(\mathcal{T}).$
Ahora para extraer los coeficientes de esta cerrado fórmula que se expanda
el logaritmo a obtener para el recuento $q_n$ la fórmula
$$n! [z^n] \sum_{k\ge 1} \frac{(-1)^{k+1}}{k}
\left(\frac{T(z)}{1-T(z)}\right)^k.$$
Observar que se puede restringir este a $k\le n$ debido a que el árbol
la función del plazo se inicia en $z,$ llegar
$$n! [z^n] \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\left(\frac{T(z)}{1-T(z)}\right)^k.$$
Todavía necesitamos los términos de la fracción en el árbol de la función,
que se puede hacer por Lagrange de la inversión. Tenemos
$$[z^n] \left(\frac{T(z)}{1-T(z)}\right)^k
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\left(\frac{T(z)}{1-T(z)}\right)^k \; dz.$$
Poner $T(z) = w$, de modo que $z=w/\exp(w)=w\exp(-w)$ y
$dz=(\exp(−w)−w\exp(−w))\; dw$ para obtener
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}}
\left(\frac{w}{1-w}\right)^k
(\exp(−w)−w\exp(−w))\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(wn)}{w^{n+1-k}}
\frac{1}{(1-w)^{k-1}} \; ps .$$
Extraer el residuo cero rendimientos para $k\ge 2$
$$\sum_{q=0}^{n-k} \frac{n^{n-k-p}}{(n-k-p)!}
{q+k-2\elegir k-2}$$
y para $k=1,$ $$\frac{n^{n-1}}{(n-1)!}.$$
La recogida de estos en una fórmula finalmente los rendimientos
$$n^n +
n! \sum_{k=2}^n \frac{(-1)^{k+1}}{k}
\sum_{q=0}^{n-k} \frac{n^{n-k-p}}{(n-k-p)!}
{q+k-2\elegir k-2}.$$
Este cálculo está estrechamente relacionado con el material de este
MSE enlace.
Adenda. Acabo de ver en uno de los otros puestos que los puntos fijos son los que no ingresaron en los endofunctions. El material anterior admite puntos fijos como en la discusión y el diagrama en la entrada de la Wikipedia.
Anexo Jue Dic 18 19:57:09 CET 2014.
El caso cuando no hay puntos fijos es el siguiente.
Ahora hay $(n-1)^n$ endofunctions sin puntos fijos,
que da $$E(z) = 1 + \sum_{n\ge 1} (n-1)^n \frac{z^n}{n!}.$$
Ahora observe que cuando aplicamos Lagrange inversión
$$\frac{\exp(-T(z))}{1-T(z)}$ $ , obtenemos
$$[z^n] \frac{\exp(-T(z))}{1-T(z)}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\frac{\exp(-T(z))}{1-T(z)}\; dz$$
que el uso de la misma sustitución como antes se convierte en
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}}
\frac{\exp(-w)}{1-w}
(\exp(−w)−w\exp(−w))\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(n-1))}{w^{n+1}}\; dw
= \frac{(n-1)^n}{n!}.$$
Pero $\exp(-T(z)) = \frac{z}{T(z)}$ y finalmente para
$E(z)$ la forma cerrada
$$\frac{z}{T(z)(1-T(z))}.$$
Esto da para $Q(z)$ que
$$Q(z) = \log\left(\frac{z}{T(z)(1-T(z))}\right)$$
(tenga en cuenta que $E(z)$ tiene un término constante en su expansión a cero, lo que
es uno) que produce la secuencia de
$$0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680,
\\ 73983185000, 2255828154624,\ldots $$
que nos señala OEIS A000435, confirmando
el resultado de la aceptación de la respuesta. Tenga en cuenta que la OEIS
dice que esta secuencia fue la primera en la base de datos, por lo que estamos
contenido a ser la referencia en este tipo de cálculos.
Para obtener una forma cerrada de re-escribir $Q(z)$ como sigue:
$$Q(z) = \log\left(1 + \frac{z}{T(z)(1-T(z))} -1\right)$$
para obtener la fórmula
$$n! [z^n] \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\left(\frac{z}{T(z)(1-T(z))} -1\right)^k$$
Este es
$$n! [z^n] \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\sum_{q=0}^k {k\elegir q} (-1)^{k-q}
\left(\frac{z}{T(z)(1-T(z))}\right)^q.$$
Podemos colocar el plazo para $q=0$ al $n\ge 1,$ llegar
$$n! [z^n] \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\sum_{q=1}^k {k\elegir q} (-1)^{k-q}
\left(\frac{z}{T(z)(1-T(z))}\right)^q.$$
El uso de Lagrange de la inversión para extraer los coeficientes de el árbol de la función
plazo.
$$[z^n] \left(\frac{z}{T(z)(1-T(z))}\right)^q
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\left(\frac{z}{T(z)(1-T(z))}\right)^q
\; dz$$
que el uso de la misma sustitución como antes se convierte en
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(n+1-q))}{w^{n+1-q}}
\left(\frac{1}{w(1-w)}\right)^q
(\exp(−w)−w\exp(−w))\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(n-q))}{w^{n+1}}
\frac{1}{(1-w)^{p-1}} \; dw$$
La extracción de los coeficientes obtenemos
$$\sum_{p=0}^n \frac{(n-q)^{n-p}}{(n-p)!} {p+q-2\choose q-2}$$
al $q\ge 2$ $q=1$
$$\frac{(n-1)^n}{n!}.$$
Sustituyendo esto en la fórmula de la suma de los rendimientos
$$n! \times \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\times k \times (-1)^{k-1} \frac{(n-1)^n}{n!}
\\ + n! \times \sum_{k=1}^n \frac{(-1)^{k+1}}{k}
\sum_{q=2}^k {k\elegir q} (-1)^{k-q}
\sum_{p=0}^n \frac{(n-q)^{n-p}}{(n-p)!} {p+q-2\elegir q-2}.$$
Esto se simplifica a
$$n\times (n-1)^n
+ n! \times \sum_{k=2}^n \frac{(-1)^{k+1}}{k}
\sum_{q=2}^k {k\elegir q} (-1)^{k-q}
\sum_{p=0}^n \frac{(n-q)^{n-p}}{(n-p)!} {p+q-2\elegir q-2}.$$
Esta fórmula puede ser usada para calcular el número de estos gráficos para
un gran $n$ donde el árbol de la función de la fórmula ya no sería
de lo posible.
La secuencia de $n=30$ $n=34$lee
38086159100543376291945674612050231296000000,
3117962569860399657478478640723143576082043800,
263711778692997479722657378560127779200642842624,
23019602620026625886784119896351926037410391377792,
2071846675499818842878197235287956993753027358752768
Observaciones adicionales.
La OEIS entrada OEIS A000435
dice que esta secuencia es la normalizado altura total de todos los etiquetados
árboles de raíces en $n$ nodos (suma de la altura de todos los nodos en todos los árboles
escala por $n$). Surge la pregunta acerca de cómo probar esto.
El parámetro de alto está representado por el bivariado de generación de
la función $T(z, u)$ donde $T(z, 1) = T(z)$ (el ordinario del árbol
función) y tenemos la ecuación funcional
$$T(z, u) = z
+ z\frac{T(uz,u)^1}{1!}
+ z\frac{T(uz,u)^2}{2!}
+ z\frac{T(uz,u)^3}{3!}
+ z\frac{T(uz,u)^4}{4!}
+ \cdots$$
o
$$T(z, u) = z \exp T(uz, u).$$
La exponencial de la generación de la función de la suma de la altura de todos
los nodos de todos los arraigada etiquetado de los árboles por el número de nodos está dada por
$$G(z) = \left.\frac{\partial}{\partial u} T(z, u)\right|_{u=1}.$$
Por lo tanto, diferenciar la ecuación funcional, consiguiendo
$$G(z) = \left. z \exp T(uz, u)
\left(z \frac{\partial}{\partial z} T(z, u) +
\frac{\partial}{\partial u} T(z, u) \right)\right|_{u=1}$$
que se convierte en
$$G(z) = T(z) (z T'(z) + G(z))$$
así que
$$G(z) (1-T(z)) = z T(z) T'(z)$$
o
$$G(z) = \frac{z T(z)}{1-T(z)} T'(z).$$
Podemos sustituir la expresión para la derivada del árbol
la función que hemos obtenido anteriormente en este para obtener
$$G(z) = \frac{z, T(z)}{1-T(z)}
\frac{1}{z} \frac{T(z)}{1-T(z)}
= \left(\frac{T(z)}{1-T(z)}\right)^2.$$
Hemos calculado la exponencial de la generación de la función de la total
la altura de todos los árboles etiquetados en $n$ nodos, que se da la secuencia
$$0, 2, 24, 312, 4720, 82800, 1662024, 37665152, 952401888,
\\ 26602156800, 813815035000 $$
que es OEIS A001864.
La normalizado altura es de esta secuencia dividida por $n.$ A comprobar que
este es de hecho el mismo que el conde de endofunctions sin fijo
punto debemos mostrar que
$$z \frac{d}{dz} Q(z) = G(z)$$
es decir, que la endofunctions veces $n$ dar la altura total o
alternativamente, la altura total dividido por $n$ dar la endofunctions.
Pero la izquierda es
$ a$ z \frac{T(z)(1-T(z))}{z} \\ \times
\left(\frac{1}{T(z)(1-T(z))}
- z \frac{1-2T(z)}
{T(z)^2 (1-T(z))^2} T'(z) \right)$$
lo que da
$$1 - z \frac{1 - 2T(z)}{T(z)(1-T(z))} T'(z)
= 1- \frac{1 - 2T(z)}{T(z)(1-T(z))} \frac{T(z)}{1-T(z)}
= 1- \frac{1 - 2T(z)}{(1-T(z))^2}
\\ = \frac{1-2T(z)+T(z)^2 -(1 - 2T(z))}{(1-T(z))^2}
= \left(\frac{T(z)}{1-T(z)}\right)^2,$$
por lo tanto la conclusión de la prueba.
