He aquí un problema de combinatoria que me preocupa mucho. Espero una respuesta rápida. Gracias de antemano. Aquí va el problema.
Inicialmente hay $n$ puntos de un círculo. Hacemos permutaciones a estos puntos de la siguiente manera: en cada permutación, los vecinos de cualquier punto son diferentes a los de la última permutación. Encontrar el número máximo de tales permutación podemos proceder.
Respuesta
¿Demasiados anuncios?
Hardik Shah
Puntos
78
Si he entendido bien tu pregunta, estás preguntando cuántos ciclos hamiltonianos de aristas disjuntas existen en el grafo completo de n vértices.
Toda disposición de personas alrededor de un círculo corresponde a un ciclo hamiltoniano en $K_n$ y si no quieres vecinos repetidos, entonces los ciclos deben ser disjuntos.
Existen $\lfloor{\frac{n-1}{2}\rfloor}$ tales ciclos, según esto: Número de ciclos hamiltonianos de arista disjunta en un grafo completo con número par de vértices.
Por lo tanto, hay tantos arreglos (incluido el primero).
