Número de DAG de orden$n$ cuya ruta más larga tiene$k$ vértices

Question

Fijar un conjunto $V$ de cardinalidad $n$. Estoy tratando de determinar el número de posibles Dag (dirigido acíclico gráficos) cuyo conjunto de vértices es $V$ con una larga ruta que contenga $k$ nodos, que voy a escribir como $D^n_k$.

Hasta el momento, he

$$ D^n_k = {n \choose k} (\ldots) $$

El $n \choose k$ es necesario porque tenemos que elegir los vértices que forman el camino más largo. También sé que la parte de los paréntesis tiene que dar el número de posibles subdiagramas de orden $n - k$, con lo cual no se extiende el camino a más de $k$ vértices, pero no sé cómo describir esto. Aunque yo después de una forma cerrada, una recurrencia, o ayuda en la obtención de uno, sería muy útil para mí.

Answer 1

(Demasiado largo para un comentario, no una respuesta completa) Si nos olvidamos de las $k$ parámetro y basta con ver el número de Dag en $n$ etiquetado de nodos , entonces el número total de Dag está dada por la recurrencia $$ D_n = \sum_{k=1}^n(-1)^{k-1}\dbinom{n}k2^{k(n-k)}D_{n-k}.$$ Si los nodos no están etiquetados, solo hay que dividir por $n!$. Este es también el OEIS secuencia A003024. Los primeros números se $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425$$ por lo $D_n$ crece muy rápidamente. Como muy crudo obligado, si tomamos solamente el primer término de la suma obtenemos $$ D_n \approx 2^nD_{n-1}$$ so $D_n \aprox 2^{n^2}$ (crece aún más rápido que el de este).

Si hacemos el mal suposición de que todos los camino más largo longitudes son igualmente probables, entonces el número de Dag en $n$ nodos etiquetados con más larga trayectoria que tienen una longitud de $k$ es aproximadamente el $\frac{D_n}k.$ sin Embargo, algunas más largas rutas de acceso son mucho más probables que otros. Más precisamente,

Si seleccionamos aleatoriamente un DAG de todos los posibles $D_n$ Dag, ¿cuál es la espera que la longitud del camino más largo ?

Si nos olvidamos de las etiquetas, y también la orientación de los bordes, es plausible creer que la cuestión es más o menos la misma pregunta

Si seleccionamos aleatoriamente un árbol fuera de todos los posibles árboles con $n$ vértices, ¿cuál es la altura del árbol?

Esta pregunta ha sido respondida aquí , y la altura es de aproximadamente el $O(\sqrt{n}).$ $k$ lejos de $O(\sqrt{n})$, podría ser mucho menos de $D_n/n$ posibilidades.