El problema de las parejas casadas

En combinatoria , el problema de las parejas casadas o el problema de los invitados ( ing.  ménage problem , fr.  problème des ménages ) pregunta de cuántas maneras diferentes pueden sentarse las parejas casadas en una mesa redonda para que personas del mismo sexo no se sienten al lado uno al lado del otro, y tampoco ningún par de cónyuges se sentó en los asientos adyacentes.

El problema fue formulado en 1891 por Eduard Luca y fue considerado de forma independiente varios años antes por Peter Tat en relación con la teoría de nudos [1] . Para el número de pares 3, 4, 5, ... el número deseado de métodos de asiento es igual a

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

Se encuentran fórmulas explícitas y recurrentes para el número de métodos de asiento . Además de usarse en etiqueta y teoría de nudos , estos números también tienen una interpretación en la teoría de grafos : dan el número de coincidencias y ciclos hamiltonianos en algunas familias de grafos.

Fórmulas

Sea M n el número de arreglos de asientos para n parejas. Tushar [2] fue el primero en obtener la fórmula:

ahora lleva su nombre. Hay muchos trabajos con pruebas de la fórmula de Touchard y sus generalizaciones, en las que se permite que partes de las parejas se sienten una al lado de la otra.

Wyman y Moser [3] dan otra fórmula que expresa M n de forma sombreada en términos de polinomios de Chebyshev del primer tipo .

Número de arreglos de asientos y el enfoque de "las damas primero"

Antes del trabajo de Bugart y Doyle [4] , la solución del problema de las parejas casadas se realizaba sentando primero a las damas y luego contando el número de asientos de los caballeros en los que el marido y la mujer no se sentaban uno al lado del otro. Sin embargo, Bugart y Doyle demostraron que la fórmula de Touchard se puede derivar directamente, sin que las damas se sienten previamente [5] .

¡ Las damas pueden sentarse 2 n ! maneras, ya que hay 2 opciones para elegir un conjunto de lugares y n ! formas de sentarse en lugares seleccionados. Para cada método de asiento, hay

formas de sentar a los caballeros, que difiere de la fórmula de Touchard solo por un factor de 2 · n ! . Esta fórmula le permite obtener una secuencia de número de parejas sentadas (comenzando con n = 3 ):

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

Satisface la relación recursiva : [6]

y una relación de recurrencia más simple: [7]

que facilitan el cálculo del número de pares de asientos.

Interpretaciones de grafos

La disposición de los asientos de las parejas casadas se puede interpretar en términos de teoría de grafos como ciclos hamiltonianos dirigidos en el gráfico de corona . La corona se obtiene eliminando un emparejamiento perfecto del grafo bipartito completo K n , n . Tiene 2 n vértices de dos colores, y cada vértice está conectado a todas las aristas del otro color, excepto a un vértice. En el problema de la pareja, los vértices representan machos y hembras, y las aristas representan pares de machos y hembras que pueden sentarse uno al lado del otro. Este gráfico se obtiene a partir de un gráfico bipartito completo eliminando una coincidencia perfecta donde los bordes conectan pares de cónyuges. Cualquier asiento adecuado de pares puede describirse mediante una secuencia de vértices, que es un ciclo hamiltoniano en un gráfico. Sin embargo, dos ciclos hamiltonianos se consideran equivalentes si conectan los mismos vértices en el mismo orden, independientemente del punto de partida, mientras que en el problema de la pareja casada, la posición de partida es significativa si, como en el caso de la fiesta del té de Alicia , todos los invitados se moverían en un asiento, sería un asiento completamente diferente, aunque es el mismo ciclo desde el punto de vista de la teoría de grafos. Por lo tanto, el número de ciclos hamiltonianos orientados en la corona es menor por un factor de 2 n en comparación con el número de asientos [8] , ¡pero más por un factor de ( n -1)! en comparación con el número de asientos. La secuencia del número de ciclos en dichos gráficos (como antes, a partir de n =3 )

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

También es posible otra descripción del problema de las parejas casadas en términos de teoría de grafos. Si las mujeres están sentadas, los posibles asientos de los hombres pueden describirse como coincidencias perfectas en el gráfico formado al eliminar un ciclo hamiltoniano de un gráfico bipartito completo. El gráfico tiene bordes que conectan los asientos vacíos con los hombres, y la eliminación del ciclo corresponde a la prohibición de que los hombres se sienten en los asientos contiguos a sus cónyuges. El número de coincidencias en un gráfico bipartito y, por lo tanto, el número de asientos, se puede calcular como un permanente de alguna matriz 0-1 . Además, para el problema de las parejas casadas, esta matriz es una circulante [9] .

Conexión con la teoría de nudos

La razón que llevó a Theta a estudiar el problema de la pareja casada provino de tratar de encontrar una lista completa de nudos matemáticos con un número dado de intersecciones , digamos n . En la notación de Dowker para diagramas de nudos, una de las primeras formas de las que utilizó Tet, los 2 n puntos eran intersecciones de nudos, que se enumeran a lo largo del nudo con números del 1 al 2 n . En el diagrama reducido, dos etiquetas de intersección no pueden ser números consecutivos, por lo que el conjunto de pares de etiquetas en cada intersección, que se usa en la notación de Dowker para denotar un nodo, puede entenderse como una combinación perfecta en un gráfico que tiene números del 1 al 2 n como vértices y aristas entre cada par de números que tienen distinta paridad 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 pares de números con diferente paridad). Por lo tanto, el número de coincidencias en dicho gráfico es igual al número de arreglos de asientos. Para nudos alternos , esta coincidencia es suficiente para describir el diagrama de nudos. Para otros nodos, se debe especificar un signo más o menos para cada intersección para describir cuál de los dos subprocesos de la intersección se encuentra en la parte superior.

Sin embargo, el problema de la enumeración de nudos tiene simetrías adicionales que no están presentes en el problema de las parejas casadas: si comenzamos desde una intersección diferente, obtenemos una notación de Dowker diferente, y todas estas notaciones deben considerarse representaciones del mismo diagrama. Por estas razones, dos coincidencias que difieren solo en la permutación cíclica deben considerarse equivalentes y solo deben contarse una vez. Hilbert [10] resolvió este problema mostrando que el número de correspondencias distintas viene dado por la secuencia:

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

Notas

  1. ↑ Dutka, 1986 .
  2. ↑ Touchard, 1934 .
  3. ↑ Wyman, Moser, 1958 .
  4. ↑ Bogart, Doyle, 1986 .
  5. ↑ Gleick, 1986 .
  6. ↑ Muir, 1882 ; Laisant, 1891 . Cayley y Muir ( Muir 1878 ) han descrito fórmulas recurrentes algo más complejas .
  7. ↑ Muir, 1882 ; Canfield, Wormald, 1987 .
  8. ↑ Passmore, 2005 .
  9. ↑ Muir, 1878 ; Eades, Praeger, Seberry, 1983 ; Krauter, 1984 ; Henderson, 1975 .
  10. ↑ Gilbert, 1956 .

Literatura

Enlaces