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.

Emparejamiento de Langford para n = 4.

El problema de Langford describe la tarea de encontrar emparejamientos de Langford para un valor n.[1]

El concepto altamente relacionado, secuencia Skolem,[2]​ se define de la misma forma, pero ésta permuta la secuencia 0, 0, 1, 1, ..., n - 1, n - 1.

Ejemplo

editar

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

Propiedades

editar

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

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, … (sucesión A014552 en OEIS).

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.

Aplicaciones

editar

Skolem (1957) usó secuencias Skolem para construir Sistemas triples de Steiner.

en los años 1960, E. J. Groth usó emparejamientos de Langford para construir circuitos para la multiplicación de enteros.[3]

Véase también

editar

Referencias

editar

Enlaces externos

editar