Emparejamiento de Langford

En combinatoria matemática, un Emparejamiento de Langford, también llamada secuencia de Langford, es una permutación de la secuencia de 2 números n 1, 1, 2, 2, ..., n, n en la cual los dos unos están una unidad separados, los dos doses están separados dos unidades, y de una forma más general dos copias de cada número k están separadas k unidades.

Los emparejamientos de Langford se llaman así gracias a C. Dudley Langford, el cual formuló el problema de su construcción en 1958.

Por ejemplo, un emparejamiento de Langford para n = 3 muestra la secuencia: 2,3,1,2,1,3.

Los emparejamientos de Lanford solo existen cuando n es congruente a 0 o 3 módulo de 4; por ejemplo, no hay emparejamiento de Langford cuando n = 1, 2, o 5.

Los números para los diferentes emparejamientos de Langford para n = 1, 2, …, contando cualquier secuencia como si fuera la misma que al invertirla, son Como describe Knuth (2008), el problema de listar todos los emparejamientos de Langford para un n dado puede ser resuelto como un caso del problema de la cobertura exacta, pero para un n más grande, el número de soluciones puede ser calculada más eficientemente con métodos algebraicos.