En matemática combinatoria , el problema de ménage o problème des ménages [1] pregunta por el número de formas diferentes en las que es posible sentar a un grupo de parejas de hombres y mujeres en una mesa redonda para que hombres y mujeres se alternen y nadie se siente al lado. a 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 del nudo . [2] Para un número de parejas igual a 3, 4, 5, ... el número de arreglos de asientos es
Los matemáticos han desarrollado fórmulas y ecuaciones de recurrencia para calcular estos números y secuencias de números relacionadas. Junto con sus aplicaciones a la etiqueta y la teoría de los nudos, estos números también tienen una interpretación de la teoría de los gráficos : cuentan el número de coincidencias y los ciclos hamiltonianos en ciertas familias de gráficos.
Fórmula de Touchard
Sea M n el número de arreglos de asientos para n parejas. Touchard (1934) derivó la fórmula
Gran parte del trabajo posterior se ha realizado en pruebas alternativas para esta fórmula y en varias versiones generalizadas del problema.
A diferente umbral fórmula para M n implica polinomios de Chebyshev de primera clase fue dada por Wyman y Moser (1958) .
Números de ménage y soluciones para mujeres
¡Hay 2 × n ! formas de sentar a las mujeres: hay dos juegos de asientos que se pueden arreglar para las mujeres, y hay n ! formas de sentarlos en un determinado conjunto de asientos. Para cada disposición de asientos para las mujeres, hay
formas de sentar a los hombres; esta fórmula simplemente omite el 2 × n ! factor de la fórmula de Touchard. Los números más pequeños resultantes (nuevamente, comenzando desde n = 3),
se llaman números de ménage . El factores el número de formas de formar k pares no superpuestos de asientos adyacentes o, de manera equivalente, el número de emparejamientos de k aristas en un gráfico cíclico de 2 n vértices. La expresión para A n es el resultado inmediato de aplicar el principio de inclusión-exclusión a arreglos en los que las personas sentadas en los extremos de cada borde de un emparejamiento deben ser una pareja.
Hasta el trabajo de Bogart y Doyle (1986) , las soluciones al problema del ménage tomaron la forma de encontrar primero todos los arreglos de asientos para las mujeres y luego contar, para cada uno de estos arreglos parciales de asientos, el número de formas de completarlo sentando a las mujeres. hombres lejos de sus parejas. Bogart y Doyle argumentaron que la fórmula de Touchard puede derivarse directamente considerando todos los arreglos de asientos a la vez en lugar de factorizar la participación de las mujeres. [3] Sin embargo, Kirousis y Kontogeorgiou (2018) encontraron la solución aún más sencilla de mujeres primero 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 ménage satisfacen la relación de recurrencia [4]
y la recurrencia de cuatro términos más simple [5]
a partir de los cuales se pueden calcular fácilmente los números de ménage.
Interpretaciones gráficas-teóricas
Las soluciones al problema de ménage pueden interpretarse en términos de teoría de grafos , como ciclos hamiltonianos dirigidos en grafos de corona . Un gráfico de corona se forma eliminando una coincidencia perfecta de un gráfico 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 de ménage, los vértices del gráfico 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 gráfico se forma eliminando la combinación perfecta formada por las parejas hombre-mujer de un gráfico 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, lo que forma un ciclo hamiltoniano en el gráfico. 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 de ménage la posición inicial se considera significativa: si, como en la fiesta del té de Alice , todos los invitados cambian sus posiciones en un asiento, se considera una disposición de asientos diferente a pesar de que se describe en el mismo ciclo. Por lo tanto, el número de ciclos hamiltonianos orientados en un gráfico de corona es menor en un factor de 2 n que el número de disposiciones de asientos, [6] ¡ pero mayor en un factor de ( n - 1)! que los números de ménage. La secuencia de números de ciclos en estos gráficos (como antes, comenzando en n = 3) es
También es posible una segunda descripción teórica de grafos del problema. Una vez que las mujeres se han sentado, la posible disposición de los asientos para los hombres restantes se puede describir como combinaciones perfectas en un gráfico formado al eliminar un solo ciclo hamiltoniano de un gráfico bipartito completo; el gráfico tiene bordes que conectan los asientos abiertos con los hombres, y la eliminación del ciclo corresponde a prohibir a los hombres sentarse en cualquiera de los asientos abiertos adyacentes a sus esposas. El problema de contar coincidencias en un gráfico bipartito y, por lo tanto, a fortiori, el problema de calcular los números de ménage, se puede resolver utilizando los permanentes de ciertas matrices 0-1 . En el caso del problema de ménage, la matriz que surge de esta visión del problema es la matriz circulante en la que todos menos dos elementos adyacentes de la fila generadora son iguales a 1 . [7]
Teoría del nudo
La motivación de Tait para estudiar el problema del ménage provino de tratar de encontrar una lista completa de nudos matemáticos con un número dado de cruces , digamos n . En la notación de Dowker para diagramas de nudos, una de las primeras formas que utilizó Tait, los 2 n puntos donde un nudo se cruza a sí mismo, en orden consecutivo a lo largo del nudo, están etiquetados 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, se puede interpretar 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 un borde entre cada par de números que tiene una paridad diferente y no son consecutivos módulo 2 n . Este gráfico se forma eliminando un ciclo hamiltoniano (conectando números consecutivos) de un gráfico 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 ménage. Para los nudos alternos , esta coincidencia es suficiente para describir el diagrama de nudos en sí; para otros nudos, es necesario 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 la lista 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 notaciones diferentes deben contarse todas como representando el mismo diagrama. Por esta razón, dos emparejamientos que se diferencian 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 ).
Ver también
- Problema de Oberwolfach , un problema matemático diferente que involucra la disposición de los comensales en las mesas
Notas
- ^ "Ménage" es lapalabra francesa para "hogar" (refiriéndose aquí a una pareja hombre-mujer).
- ^ Dutka (1986) .
- ^ Gleick (1986) .
- ↑ Muir (1882) ; Laisant (1891) . Cayley y Muir (1878) habían descrito anteriormente recurrencias más complicadas.
- ↑ Muir (1882) ; Canfield y Wormald (1987) .
- ^ Passmore (2005) .
- ↑ Muir (1878) ; Eades, Praeger y Seberry (1983) ; Kräuter (1984) ; Henderson (1975) .
Referencias
- Bogart, Kenneth P .; Doyle, Peter G. (1986), "Solución no sexista del problema de ménage" , American Mathematical Monthly , 93 (7): 514–519, doi : 10.2307 / 2323022 , JSTOR 2323022 , MR 0856291.
- Bong, Nguyen-Huu (1998), "Lucas numbers and the menage problem", International Journal of Mathematical Education in Science and Technology , 29 (5): 647–661, doi : 10.1080 / 0020739980290502 , MR 1649926.
- Canfield, E. Rodney; Wormald, Nicholas C. (1987), "Ménage numbers, bijections and P-recursivity", Discrete Mathematics , 63 (2-3): 117-129, doi : 10.1016 / 0012-365X (87) 90002-1 , MR 0885491.
- Dörrie, Heinrich (1965), "El problema de Lucas de las parejas casadas", 100 grandes problemas de matemáticas elementales , Dover, págs. 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, doi : 10.1007 / BF03025785 , MR 0846991.
- Eades, Peter ; Praeger, Cheryl E .; Seberry, Jennifer R. (1983), "Algunas observaciones sobre las permanentes de matrices circulantes (0,1)", Utilitas Mathematica , 23 : 145-159, MR 0703136.
- Gilbert, EN (1956), "Nudos y clases de permutaciones de ménage", Scripta Mathematica , 22 : 228-233, MR 0090568.
- Gleick, James (28 de octubre de 1986), "Matemáticas + sexismo: un problema" , New York Times.
- Henderson, JR (1975), "Permanentes de (0,1) -matrices que tienen como máximo dos ceros por línea", Canadian Mathematical Bulletin , 18 (3): 353–358, doi : 10.4153 / CMB-1975-064-6 , MR 0399127.
- Holst, Lars (1991), "On the 'problème des ménages' desde un punto de vista probabilístico", Statistics and Probability Letters , 11 (3): 225-231, doi : 10.1016 / 0167-7152 (91) 90147-J , MR 1097978.
- Kaplansky, Irving (1943), "Solution of the problème des ménages", Bulletin of the American Mathematical Society , 49 (10): 784–785, doi : 10.1090 / S0002-9904-1943-08035-4 , MR 0009006.
- 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 , París: Gauthier-Villars, págs. 491–495.
- Muir, Thomas (1878), "Sobre el problema del arreglo del profesor Tait", Actas de la Royal Society of Edinburgh , 9 : 382–391. Incluye (págs. 388–391) una adición de Arthur Cayley .
- Muir, Thomas (1882), "Nota adicional sobre un problema de arreglo", Actas de la Royal Society of Edinburgh , 11 : 187-190.
- Passmore, Amanda F. (2005), Una solución elemental al problema de ménage , CiteSeerX 10.1.1.96.8324.
- Riordan, John (1952), "La aritmética de los números ménage", Duke Mathematical Journal , 19 (1): 27–30, doi : 10.1215 / S0012-7094-52-01904-2 , MR 0045680.
- Takács, Lajos (1981), "On the" problème des ménages " ", Discrete Mathematics , 36 (3): 289-297, doi : 10.1016 / S0012-365X (81) 80024-6 , MR 0675360.
- Touchard, J. (1934), "Sur un problema de permutaciones" , CR Acad. Sci. París , 198 (631–633).
- Wyman, Max; Moser, Leo (1958), "On the problème des ménages", Canadian Journal of Mathematics , 10 (3): 468–480, doi : 10.4153 / cjm-1958-045-6 , MR 0095127.
enlaces externos
- Weisstein, Eric W. "Problema de las parejas casadas" . MathWorld .
- Weisstein, Eric W. "Fórmula de recurrencia de Laisant" . MathWorld .