Cuántos débilmente conectados a los bigramas de n vértices tiene sin bucles y cuyos vértices tienen todos indegree 1?

Question

Cuántos bucles, débilmente conectados a los bigramas de n vértices tiene cuyos vértices tienen todos indegree 1?

Aquí hay dos ejemplos de tales bigramas con $n = 5$:

• $v_1 \to \{v_2, v_3, v_4, v_5\}; \; v_5 \to v_1$
• $v_1 \to v_2; \; v_2 \to v_3; \; v_3 \to v_4; \; v_4 \to v_5; \; v_5 \to v_1$

Hay un teorema o fórmula que describe el número de estos de los bigramas que existen para $n$ vértices, hasta el isomorfismo?

---

Actualización: Un comentarista pidió algunos antecedentes.

Estoy escribiendo un rompecabezas de un juego que el jugador debe resolver. El jugador activa una serie de haz de emisores-receptores (BER) en diversas posiciones. Cada BER sólo puede recibir una viga, pero puede emiten tantos como se quiere a los otros Miembros.

El rompecabezas se resuelve cuando cada BER está recibiendo energía a partir de algunos otros REC. Estoy curioso sobre el número de combinaciones que se pueden lograr con un n-configuración de la instancia de BERs, así que le pregunté a esta pregunta.

Answer 1

Me acabo de dar cuenta de que pidió el número de gráficos diferentes a isomorfismo, es decir, sin etiquetar los vértices. El número que aparece a continuación es el número de diferentes gráficos con etiquetas de los vértices, es decir, contar isomorfo gráficos con diferentes vértice etiquetas como algo distinto.

---

Yo, básicamente, contados estos gráficos en esta respuesta. Desde cada vértice tiene indegree $1$, no debe ser $n$ bordes. No puede haber más de un par de vértices con bordes va en ambos sentidos, ya que de lo contrario el grafo no dirigido asociado en la mayoría de los $n-2$ bordes y por lo tanto no estar conectado. Si hay un par, se puede considerar como un "$2$-ciclo" y tratar esto como un caso especial de un ciclo. Si no hay pareja, los asociados de grafo no dirigido es un grafo conexo de $n$ vértices con $n$ bordes. Como Rahul señaló en un comentario, esta debe ser de un solo ciclo con una (posiblemente trivial) árbol arraigado en cada vértice del ciclo.

Ahora sólo queda determinar el número de formas de asociar un dígrafo con estos grafo gráficos. La dirección de los bordes de los árboles es fijo, y hay dos opciones para la dirección de los bordes en el ciclo. Por lo tanto, el número de gráficos es sólo dos veces el número de grafo gráficos,

$$(n-1)!\sum_{k=2}^n\frac{n^{n-k}}{(n-k)!}\;,$$

donde se puede comprobar que el $k=2$ caso sale a la derecha observando que hay $n^{n-2}$ árboles en $n$ vértices y podemos elegir las dos vías de borde como uno de $n-1$ bordes en cada uno de estos árboles.