Problema de menage

En matemáticas combinatorias , el problema del ménage o problème des ménages pregunta por el número de maneras diferentes en que es posible sentar a un conjunto de parejas de hombre y mujer en una mesa de comedor redonda de modo que los hombres y las mujeres se alternen y nadie se siente al lado de su pareja. ( Ménage es la palabra francesa para "hogar", refiriéndose aquí a una pareja de hombre y mujer). 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 . ^[1] Para un número de parejas igual a 3, 4, 5, ... el número de arreglos de asientos es

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (secuencia A059375 en la OEIS ).

Los matemáticos han desarrollado fórmulas y ecuaciones de recurrencia para calcular estos números y secuencias de números relacionadas . Además de sus aplicaciones a la etiqueta y la teoría de nudos, estos números también tienen una interpretación teórica de grafos : cuentan la cantidad de coincidencias y ciclos hamiltonianos en ciertas familias de grafos .

Sea M _n el número de asientos para n parejas. Touchard (1934) derivó la fórmula

${\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!.}$

Mucho trabajo posterior se ha dedicado a encontrar pruebas alternativas de esta fórmula y a varias versiones generalizadas del problema.

Wyman y Moser (1958) dieron una fórmula umbral diferente para M _n que involucra polinomios de Chebyshev de primer tipo .

Hay 2× n ! formas de sentar a las mujeres: hay dos conjuntos de asientos que se pueden disponer para las mujeres, y hay n ! formas de sentarlas en un conjunto particular de asientos. Para cada disposición de asientos para las mujeres, hay

${\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!}$

formas de colocar a los hombres; esta fórmula simplemente omite el factor 2× n ! de la fórmula de Touchard. Los números resultantes más pequeños (de nuevo, comenzando desde n  = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (secuencia A000179 en la OEIS )

se denominan números de ménage . El factor es el número de formas de formar k pares no superpuestos de asientos adyacentes o, equivalentemente, el número de emparejamientos de k aristas en un grafo cíclico de 2n vértices . La expresión para A _n es el resultado inmediato de aplicar el principio de inclusión-exclusión a disposiciones en las que se requiere que las personas sentadas en los puntos finales de cada arista de un emparejamiento sean una pareja. ${\displaystyle {\frac {2n}{2n-k}}{2n-k \elige k}}$

Hasta el trabajo de Bogart y Doyle (1986), las soluciones al problema del ménage consistían en encontrar primero todas las disposiciones de asientos para las mujeres y luego contar, para cada una de estas disposiciones de asientos parciales, la cantidad de formas de completarlo sentando a los hombres lejos de sus parejas. Bogart y Doyle argumentaron que la fórmula de Touchard se puede derivar directamente considerando todas las disposiciones de asientos a la vez en lugar de factorizar la participación de las mujeres. ^[2] Sin embargo, Kirousis y Kontogeorgiou (2018) encontraron la solución aún más sencilla de las mujeres primero descrita anteriormente haciendo uso de algunas de las ideas de Bogart y Doyle (aunque tuvieron cuidado de reformular el argumento en un lenguaje no sexista).

Los números de ménage satisfacen la relación de recurrencia ^[3]

${\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}$

y la recurrencia más simple de cuatro términos ^[4]

${\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4},}$

a partir de lo cual se pueden calcular fácilmente los números del ménage.

Las soluciones al problema del ménage pueden interpretarse en términos de teoría de grafos , como ciclos hamiltonianos dirigidos en grafos de corona . Un grafo de corona se forma eliminando una coincidencia perfecta de un grafo bipartito completo K _n,n ; tiene 2 n vértices de dos colores, y cada vértice de un color está conectado a todos menos uno de los vértices del otro color. En el caso del problema del ménage, los vértices del grafo representan hombres y mujeres, y los bordes representan pares de hombres y mujeres a los que se les permite sentarse uno al lado del otro. Este grafo se forma eliminando la coincidencia perfecta formada por las parejas hombre-mujer de un grafo bipartito completo que conecta a cada hombre con cada mujer. Cualquier disposición de asientos válida se puede describir por la secuencia de personas en orden alrededor de la mesa, que forma un ciclo hamiltoniano en el grafo. 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 ménage la posición inicial se considera significativa: si, como en la fiesta del té de Alicia , todos los invitados cambian sus posiciones un asiento, se considera una disposición de asientos diferente aunque esté descrita por el mismo ciclo. Por lo tanto, el número de ciclos hamiltonianos orientados en un grafo de corona es menor por un factor de 2 n que el número de disposiciones de asientos, ^[5] pero mayor por un factor de ( n  − 1)! que los números del ménage. La secuencia de números de ciclos en estos grafos (como antes, comenzando en n  = 3) es

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (secuencia A094047 en la OEIS ).

También es posible una segunda descripción del problema desde el punto de vista de la teoría de grafos. Una vez que las mujeres se han sentado, las posibles disposiciones de asientos para los hombres restantes pueden describirse como emparejamientos perfectos en un grafo formado eliminando un único ciclo hamiltoniano de un grafo bipartito completo; el grafo tiene aristas que conectan los asientos libres 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. El problema de contar emparejamientos en un grafo bipartito , y por lo tanto a fortiori el problema de calcular los números de ménage, puede resolverse utilizando los permanentes de ciertas matrices 0-1 . En el caso del problema del ménage, la matriz que surge de esta visión del problema es la matriz circulante en la que todos los elementos adyacentes, excepto dos, de la fila generadora son iguales a 1. ^[6]

La motivación de Tait para estudiar el problema del ménage surgió de intentar encontrar una lista completa de nudos matemáticos con un número dado de cruces , digamos n . En la notación Dowker para diagramas de nudos, una forma temprana de la cual fue utilizada por Tait, los 2 n puntos donde un nudo se cruza consigo mismo, en orden consecutivo a lo largo del nudo, se etiquetan con los 2 n números del 1 al 2 n . En un diagrama reducido, las dos etiquetas en un cruce no pueden ser consecutivas, por lo que el conjunto de pares de etiquetas en cada cruce, utilizado en la notación Dowker para representar el nudo, puede interpretarse como una coincidencia perfecta en un gráfico que tiene un vértice para cada número en el rango de 1 a 2 n y una arista entre cada par de números que tiene diferente paridad y no son consecutivos módulo 2 n . Este gráfico se forma eliminando un ciclo hamiltoniano (que conecta números consecutivos) de un gráfico bipartito completo (que conecta todos los pares de números con diferente paridad), por lo que tiene un número de coincidencias igual a un número de ménage. Para los nudos alternados , esta coincidencia es suficiente para describir el diagrama de nudos en sí; para otros nudos, se debe especificar un signo positivo o negativo adicional para cada par de cruces para determinar cuál de las dos hebras del cruce se encuentra por encima de la otra hebra.

Sin embargo, el problema de enumeración de nudos tiene algunas simetrías adicionales que no están presentes en el problema de ménage: se obtienen diferentes notaciones de Dowker para el mismo diagrama de nudos si se comienza el etiquetado en un punto de cruce diferente, y estas diferentes notaciones deben contarse todas como si representaran el mismo diagrama. Por esta razón, dos emparejamientos 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 emparejamientos diferentes es

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (secuencia A002484 en la OEIS ).

• Problema de Oberwolfach , un problema matemático diferente que involucra la disposición de los comensales en las mesas.
• Problème des rencontres , un problema similar que implica trastornos parciales

• Weisstein, Eric W. "El problema de las parejas casadas". MathWorld .
• Weisstein, Eric W. "Fórmula de recurrencia de Laisant". MathWorld .