Vamos a ser $G=(U,V,E)$ un bipartito gráfico donde $U$ $K$ posibles vértices y $V$ $N$ posibles vértices.
Nos centramos en cerrado los caminos de la longitud de la $2L$. Tales paseos pueden ser descritos por la secuencia de vértices $(u_1,v_1,u_2,v_2,\ldots,u_L,v_L,u_1)$. El $(2k-1)$th borde está dado por $\{ u_k,v_k \}$ e las $2k$th borde está dado por $\{v_k,u_{k+1}\}$$1\leq k\leq L-1$, los dos últimos son los bordes $\{u_L,v_L\}$, $\{v_L,u_1\}$. Las siguientes dos propiedades tienen que ser satisfechos:
(P1) $u_k\neq u_{k+1}$$1\leq k\leq L-1$$u_L\neq u_1$;
(P2) de cada borde se recorre un número par de veces.
La pregunta es: ¿cuántos cerrado paseos satisfactorio (P1) y (P2) ha $\ell$ bordes definidos?
Ejemplo: $U = \{1,2,3\}$, $V=\{4,5\}$. El paseo $(1,4,2,5,2,4,1)$ no satisface (P1), ya que se trata de volver a $2$ después $5$, mientras que por ejemplo, $(1,4,2,4,1)$ es aceptar.
Puedo resolver el problema al $N=1$, ya que en ese caso (P2) es satisfecho automáticamente (el grafo es bipartito, pero en este caso muy particular $V$ tiene un solo vértice, etc...) mientras que no sé cómo empezar cuando $N>1$. ¿Tiene usted alguna sugerencia?
P. S. tengo un algoritmo que calcule (fuerza bruta), en la respuesta dada $K$, $N$, $L$. He aquí un informe de cuatro casos con elecciones aleatorias de $K$, $N$, $L$ para algunos de verificación, espero que les puede ser útil: cuando $K=7$, $N=3$, $L=3$, a continuación, $(1134,630)$ el número de cerrado camina con $\ell=2,3$ bordes definidos; cuando $K=7$, $N=1$, $L=4$, a continuación, $(294,1260,840)$ $\ell=2,3,4$ bordes definidos; cuando $K=7$, $N=2$, $L=4$, a continuación, $(2100,4200,2772)$ $\ell=2,3,4$ bordes definidos; cuando $K=7$, $N=3$, $L=4$, a continuación, $(6930,8820,5796)$ $\ell=2,3,4$ bordes definidos.
Actualización (combinatoria formulario): creo que puede reformular el problema de la siguiente forma combinatoria. Dejar cerrada paseo de ser representada por el conjunto de sus bordes: \begin{equation}\mathcal{G}=\{ \{u_1,v_1\},\{v_1,u_2\},\{u_2,v_2\},\ldots,\{u_L,v_L\},\{v_L,u_1\} \}.\end{equation} Este es un conjunto debidamente especificados por la fijación de $(u_1,\ldots,u_L)$ $(v_1,\ldots,v_L)$ donde$1 \leq u_k \leq K$$1 \leq v_k \leq N$. Los elementos son en realidad conjuntos de la forma $\{u_i,v_j\}$. Supongamos que hay $\ell$ distintos elementos de este conjunto. Para (P2), se tiene: \begin{equation} 2L = 2n_1 + \cdots + 2n_\ell,\end{equation} donde $2n_i$ es el número de veces que el $i$th aparece. Este número es necesariamente, y $L=n_1+\cdots+n_\ell$. Hay un número de maneras de obtener esta suma y este está dado por una fórmula estándar en la combinatoria. Cuántas $\mathcal{G}$ satisfactorio (P1) hay? En otras palabras, ¿cuántas veces $\mathcal{G}$ $\ell$ elementos distintos, cada uno que aparece un número par de veces, satisfactorio (P1)?
