Problema del menaje

Una mesa con diez cubiertos. Hay 3120 formas diferentes en las que cinco parejas de hombres y mujeres pueden sentarse en esta mesa, de modo que hombres y mujeres se alternan y nadie se siente al lado de su pareja.

En combinatoria, el problema del menaje o problema de las parejas de comensales​ consiste en determinar el número de maneras diferentes en las que es posible sentar a un grupo de parejas de hombres y mujeres en una mesa de comedor redonda para que se alternen hombres y mujeres y nadie se siente al lado de su pareja. 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.​ Para un número de parejas igual a 3, 4, 5, ... el número de maneras distintas de sentarlas es:

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sucesión A059375 en OEIS).

Los matemáticos han desarrollado fórmulas y relaciones de recurrencia para calcular estos números y las secuencias de números relacionadas. Junto con sus aplicaciones a la etiqueta y la teoría de nudos, estos números también tienen una interpretación en la teoría de grafos: cuentan los números de emparejamientos y de ciclos hamiltonianos en ciertas familias de grafos.

Fórmula de Touchard

Sea M_n el número de posibles distribuciones de asientos para n parejas.Touchard (1934) obtuvo la fórmula

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

Gran parte del trabajo posterior se ha centrado en pruebas alternativas para esta fórmula y en varias versiones generalizadas del problema.

Mediante el se dispone de

Una fórmula umbral diferente que involucra a los polinomios de Chebyshov de primera especie fue dada por Wyman y Moser (1958) para M_n.

Números de menaje y soluciones para damas primero

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

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

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

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (sucesión A000179 en OEIS)

y se llaman números de menaje. El factor ${\frac {2n}{2n-k}}{2n-k \choose k}$ es el número de maneras de formar k pares no superpuestos de asientos adyacentes o, de manera equivalente, el número de emparejamientos de k vínculos en un grafo ciclo 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 extremos de cada vínculo sean los miembros de una de las parejas de invitados.

Hasta el trabajo de Bogart y Doyle (1986), las soluciones al problema del menaje 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, el número de formas de completarlas sentando a los hombres lejos de sus parejas. Bogart y Doyle argumentaron que la fórmula de Touchard puede derivarse directamente al considerar todas las disposiciones de asientos a la vez en lugar de descartar la participación de las mujeres.​ Sin embargo,Kirousis y Kontogeorgiou (2018) encontró la solución aún más sencilla de dar prioridad a las mujeres descrita anteriormente al hacer uso de algunas de las ideas de Bogart y Doyle (aunque se cuidaron de reformular el argumento en un lenguaje sin género).

Los números de menaje satisfacen la relación de recurrencia​

$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​

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

a partir de la cual se pueden calcular fácilmente los propios números de menaje.

Interpretaciones en teoría de grafos

Grafos en corona con seis, ocho y diez vértices. El ciclo exterior de cada grafo forma un ciclo hamiltoniano; los grafos de ocho y diez vértices también tienen otros ciclos hamiltonianos

Las soluciones al problema del menaje pueden interpretarse en términos de la teoría de grafos, como grafos de corona con ciclos hamiltonianos dirigidos. Un grafo de corona se forma eliminando un emparejamiento perfecto de un grafo bipartito completo K_n,n; tiene 2n 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 menaje, los vértices del grafo representan hombres y mujeres, y las aristas representan parejas de hombres y mujeres que pueden sentarse uno al lado del otro. 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. Cualquier disposición de asientos válida puede describirse mediante 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 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. Por lo tanto, el número de ciclos hamiltonianos orientados en un grafo de corona es menor por un factor de 2n que el número de disposiciones de asientos,​ pero mayor por un factor de (n −  1)! que los números de menaje. La secuencia de números de ciclos en estos grafos (como antes, comenzando en n = 3) es

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (sucesión A094047 en OEIS).

También es posible una segunda descripción teórica de grafos del problema. 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. El problema de contar coincidencias en un grafo bipartito, y por lo tanto a fortiori el problema de calcular números de menaje, puede resolverse utilizando los permanentes de ciertas matrices formadas por 0-1. En el caso del problema del menaje, la matriz que surge de esta vista del problema es la matriz circulante en la que todos los elementos adyacentes de la fila generadora excepto dos son iguales a 1.​

Teoría de nudos

La motivación de Tait para estudiar el problema del menaje provino de tratar de encontrar una lista completa de nudos matemáticos con un número de cruces dado, como por ejemplo n. En la notación de Dowker para diagramas de nudos, una forma temprana utilizada por Tait, los puntos 2n donde un nudo se cruza a sí mismo, en orden consecutivo en el nudo, están etiquetados con los números 2n del 1 a 2n. 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, usado en la notación de Dowker para representar el nudo, puede interpretarse como una coincidencia perfecta en un grafo que tiene un vértice para cada número en el rango de 1 a 2n y una arista entre cada par de números que tiene diferente paridad y no son consecutivos módulo 2n. Este grafo se forma eliminando un ciclo hamiltoniano (conectando números consecutivos) de un grafo bipartito completo (conectando todos los pares de números con diferente paridad), por lo que tiene un número de coincidencias igual a un número de menaje. Para nudos alternos, 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 con el fin de determinar cuál de los dos hilos del cruce se encuentra por encima del otro hilo.

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

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (sucesión A002484 en OEIS).

Véase también

• Problema de Oberwolfach, un problema matemático similar relacionado con la disposición de los comensales en una mesa
• Problema de encuentros, otro problema parecido que contempla restricciones parciales

Bibliografía

• Bogart, Kenneth P.; Doyle, Peter G. (1986), «Non-sexist solution of the ménage problem», American Mathematical Monthly 93 (7): 514-519, JSTOR 2323022, MR 0856291, doi:10.2307/2323022 ..
• Bong, Nguyen-Huu (1998), «Lucas numbers and the menage problem», International Journal of Mathematical Education in Science and Technology 29 (5): 647-661, MR 1649926, doi:10.1080/0020739980290502 ..
• Canfield, E. Rodney; Wormald, Nicholas C. (1987), «Ménage numbers, bijections and P-recursiveness», Discrete Mathematics 63 (2–3): 117-129, MR 0885491, doi:10.1016/0012-365X(87)90002-1 ..
• Dörrie, Heinrich (1965), «Lucas' Problem of the Married Couples», 100 Great Problems of Elementary Mathematics, Dover, pp. 27-33, ISBN 978-0-486-61348-2 .. Traducido por David Antin.
• Dutka, Jacques (1986), «On the problème des ménages», The Mathematical Intelligencer 8 (3): 18-33, MR 0846991, doi:10.1007/BF03025785 ..
• Eades, Peter; Praeger, Cheryl E.; Seberry, Jennifer R. (1983), «Some remarks on the permanents of circulant (0,1) matrices», Utilitas Mathematica 23: 145-159, MR 0703136 ..
• Gilbert, E. N. (1956), «Knots and classes of ménage permutations», Scripta Mathematica 22: 228-233, MR 0090568 ..
• Gleick, James (28 de octubre de 1986), «Math + Sexism: A Problem», The New York Times ..
• Henderson, J. R. (1975), «Permanents of (0,1)-matrices having at most two zeros per line», Canadian Mathematical Bulletin 18 (3): 353-358, MR 0399127, doi:10.4153/CMB-1975-064-6 ..
• Holst, Lars (1991), «On the ‘problème des ménages’ from a probabilistic viewpoint», Statistics and Probability Letters 11 (3): 225-231, MR 1097978, doi:10.1016/0167-7152(91)90147-J ..
• Kaplansky, Irving (1943), «Solution of the problème des ménages», Bulletin of the American Mathematical Society 49 (10): 784-785, MR 0009006, doi:10.1090/S0002-9904-1943-08035-4 ..
• Kaplansky, Irving; Riordan, J. (1946), «The problème des ménages», Scripta Mathematica 12: 113-124, MR 0019074 ..
• Kirousis, L.; Kontogeorgiou, G. (2018), «102.18 The problème des ménages revisited», The Mathematical Gazette 102 (553): 147-149, arXiv:1607.04115, doi:10.1017/mag.2018.27 ..
• Kräuter, Arnold Richard (1984), «Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen», Séminaire Lotharingien de Combinatoire (en alemán), B11b ..
• Laisant, Charles-Ange (1891), «Sur deux problèmes de permutations», Vie de la société, Bulletin de la Société Mathématique de France (en francés) 19: 105-108 ..
• Lucas, Édouard (1891), Théorie des Nombres, Paris: Gauthier-Villars, pp. 491-495 ..
• Muir, Thomas (1878), «On Professor Tait's problem of arrangement», Proceedings of the Royal Society of Edinburgh 9: 382-391 .. Incluye (págs. 388–391) una adición de Arthur Cayley.
• Muir, Thomas (1882), «Additional note on a problem of arrangement», Proceedings of the Royal Society of Edinburgh 11: 187-190 ..
• Passmore, Amanda F. (2005), An elementary solution to the ménage problem, «citeseerx: 10.1.1.96.8324» ..
• Riordan, John (1952), «The arithmetic of ménage numbers», Duke Mathematical Journal 19 (1): 27-30, MR 0045680, doi:10.1215/S0012-7094-52-01904-2 ..
• Takács, Lajos (1981), «On the "problème des ménages"», Discrete Mathematics 36 (3): 289-297, MR 0675360, doi:10.1016/S0012-365X(81)80024-6 ..
• Touchard, J. (1934), «Sur un problème de permutations», C. R. Acad. Sci. Paris 198 (631–633) ..
• Wyman, Max; Moser, Leo (1958), «On the problème des ménages», Canadian Journal of Mathematics 10 (3): 468-480, MR 0095127, doi:10.4153/cjm-1958-045-6 ..

Enlaces externos

• Weisstein, Eric W. «Married Couples Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Laisant's Recurrence Formula». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q3406269