Problema del menaje
Este problema fue formulado en 1891 por Édouard Lucas e independientemente, unos años antes, por Peter Guthrie Tait en relación con la teoría de nudos.
Sea Mn el número de posibles distribuciones de asientos para n parejas.Touchard (1934) obtuvo la fórmula Gran parte del trabajo posterior se ha centrado en pruebas alternativas para esta fórmula y en varias versiones generalizadas del problema.
maneras de sentar a las mujeres: hay dos juegos de asientos que se pueden disponer para las mujeres, y hay n!
Este grafo se forma eliminando la combinación perfecta formada por las parejas hombre-mujer de un grafo bipartito completo que conecta a cada hombre con cada mujer.
Sin embargo, dos ciclos hamiltonianos se consideran equivalentes si conectan los mismos vértices en el mismo orden cíclico independientemente del vértice inicial, mientras que en el problema del menaje la posición inicial se considera significativa: si, como en la fiesta del té de Alicia en el país de las maravillas, todos los invitados cambian sus posiciones en un asiento, se considera una disposición de asientos diferente aunque esté descrita por el mismo ciclo.
Una vez que las mujeres se han sentado, las posibles disposiciones de asientos para los hombres restantes se pueden describir como emparejamientos perfectos en un grafo formado al eliminar un solo ciclo hamiltoniano de un grafo bipartito completo; el grafo tiene aristas que conectan los asientos restantes con los hombres, y la eliminación del ciclo corresponde a prohibir a los hombres sentarse en cualquiera de los asientos libres adyacentes a sus esposas.
Sin embargo, el problema del listado de nudos tiene algunas simetrías adicionales que no están presentes en el problema del menaje: se obtienen diferentes notaciones de Dowker para el mismo diagrama de nudos si se comienza el etiquetado en un punto de cruce diferente, y todas estas notaciones diferentes deben contarse como que representan el mismo diagrama.
Por esta razón, dos coincidencias que difieren entre sí por una permutación cíclica deben tratarse como equivalentes y contarse solo una vez.Gilbert (1956) resolvió este problema de enumeración modificado, mostrando que el número de coincidencias diferentes es
