Número de dígrafos acíclicos en $[n]$ $k$ aristas y cada indegree, outdegree $\leq 1$

Question

Dígrafos acíclicos (etiquetados) ¿cuántos hay en la cima establecen $[n]$ aristas exactamente $k$, cada indegree y outdegree $\leq 1$? La respuesta es $${n \choose k} {n-1 \choose k} k!.$$ Is there a bijective proof? I imagine the ${n \choose k} %#% indicador de #! $ podría representar poner una estructura de orden o ciclo en estos vértices, pero no estoy seguro de lo que podría representar el otro factor.

Answer 1

Cualquier acíclicos dígrafo en el vértice set $[n]$ con exactamente $k$ bordes y cada indegree, outdegree $\leq 1$ consistirá $n-k$ componentes, cada uno de los cuales es esencialmente una lista ordenada, o tupla. (Empezando sin bordes y $n$ tuplas, la adición de borde de $(i,j)$ a de la gráfica es equivalente a la concatenación de la tupla que comienzan con $j$ hacia el final de la tupla que termina en $i$. Por lo tanto el aumento del número de bordes por $1$ disminuye el número de tuplas por $1$.) Por tanto, el problema es equivalente a contar el número de maneras de partición de la $[n]$ a $n-k$ no vacío tuplas.

Para la construcción de $n-k$ no vacío tuplas de $n$ elementos, en primer lugar elija una permutación de $n$ elementos. Esto se puede hacer en $n!$ maneras. A continuación, elija $n-k-1$ de la $n-1$ posibles puntos de corte en la permutación para crear $n-k$ no vacío tuplas. Esto se puede hacer en $\binom{n-1}{n-k-1} = \binom{n-1}{k}$ maneras. Sin embargo, como no se $(n-k)!$ formas de orden de las tuplas, hay $(n-k)!$ permutaciones que crear el mismo conjunto de $n-k$ no vacío tuplas. Por tanto, el número de maneras en que un conjunto de $n$ elementos se puede dividir en $n-k$ no vacío tuplas es $$\frac{n!}{(n-k)!} \binom{n-1}{k} = \binom{n}{k} \binom{n-1}{k} k!.$$

(Por cierto, el número de formas de partición de la $[n]$ a $k$ no vacío tuplas es conocido por ser el Lah número $L(n,k)$.)

Answer 2

He aquí otra manera de contar. Como usted dice, $\binom nk$ puede ser visto como el número de formas de elegir a $k$ vértices como jefes de la $k$ bordes. Ahora elija las colas de estos jefes, uno por uno. Hay $n-1$ posibilidades para la elección de una cola para la primera cabeza. En la elección de una cola para la $i$-ésimo de la cabeza, $i\gt1$, hay dos casos. El $i$-th cabeza no ha sido elegido como una cola todavía; luego $i-1$ vértices son excluidos porque ya han sido elegidas como las colas, y el $i$-ésimo de la cabeza es diferente de ellos y también excluidos, dejando $n-i$ posibilidades. O $i$-th cabeza ya ha sido elegida como una cola; entonces el $i$-ésimo de la cabeza es una de las $i-1$ vértices excluidos por ya haber sido elegido como una cola, pero no es exactamente un vértice en la cabeza de la cadena que conduce a la $i$-ésimo de la cabeza que no ha sido elegida como una cola pero es excluido debido a que la elección se crearía un ciclo. Así, en cualquier caso no se $n-i$ posibilidades, por lo que en todos hay

$$ \binom nk(n-1)\dotso(n-k)=\binom nk\binom{n-1} kk!\;. $$

Answer 3

Este problema también puede ser respondidas mediante la bivariante (mixto) la generación de la función $$ G(z, u) = \sum_{n\ge 1} \sum_{k=0}^{n-1} q_{n,k} \; u^k \frac{z^n}{n!} $$ donde $q_{n,k}$ es el recuento de los acíclicos de los bigramas en $n$ nodos y con $k$ bordes que queremos encontrar, y por lo tanto está dado por $$ q_{n,k} = n! [u^k z^n] G(z, u).$$

Como se ha señalado los gráficos en cuestión son esencialmente conjuntos de listas ordenadas, de modo que su combinatoria especificaciones de clase es $$\mathcal{G} = \mathfrak{P}(\mathcal{L})$$ donde $\mathcal{L}$ es la clase de listas ordenadas. Con $L(z, u)$ siendo la mezcla de la generación de la función de ordenada etiquetados listas, esto se traduce en $$ G(z, u) = \exp L(z, u).$$ Pero $L(z, u)$ es fácil de obtener en forma cerrada, tenemos $$ L(z, u) = \sum_{n\ge 1} n! u^{n-1} \frac{z^n}{n!} = z \sum_{n\ge 1} (uz)^{n-1} = \frac{z}{1-uz}$$ y así $$ G(z, u) = \exp\left(\frac{z}{1-uz}\right).$$ Para completar el cálculo, hay que recordar que la $$ [z^n] \frac{1}{(1-z)^s} = \binom{n+s-1}{s-1}$$ dando $$ n! [u^k z^n] G(z, u) = n! [u^k z^n] \sum_{m\ge 0} \frac{1}{m.} \left(\frac{z}{1-uz}\right)^m = n! [u^k] \sum_{m=0}^n \frac{1}{m.} [z^n]\left(\frac{z}{1-uz}\right)^m $$ que es $$n! [u^k] \sum_{m=0}^n \frac{1}{m.} [z^{n-m}] \frac{1}{(1-uz)^m} = n! [u^k] \sum_{m=0}^n \frac{1}{m.} u^{n-m} \binom{n-m+m-1}{m-1} \\= n! [u^k] \sum_{m=0}^n \frac{1}{m.} u^{n-m} \binom{n-1}{m-1}.$$ Ahora interruptor de variables en la suma para obtener $$ n! [u^k] \sum_{m=0}^n \frac{1}{(n-m)!} u^m \binom{n-1}{n-m-1} = n! [u^k] \sum_{m=0}^n \frac{1}{(n-m)!} u^m \binom{n-1}{m} = n!\frac{1}{(n-k)!} \binom{n-1}{k} = \binom{n}{k} \binom{n-1}{k} k!. $$

Hay más información sobre esta hermosa método en este enlace en el INRIA.