Emparejamiento de Langford

Emparejamiento de Langford para n = 4.

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.

El problema de Langford describe la tarea de encontrar emparejamientos de Langford para un valor n.​

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

Ejemplo

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

Propiedades

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

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

Véase también

• Permutación de Stirling, un tipo diferente de permutación del mismo multiconjunto

Referencias

• Gardner, Martin (1978), «Langford's problem», Mathematical Magic Show, Vintage, p. 70 ..
• Knuth, Donald E. (2008), The Art of Computer Programming, Vol. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley, ISBN 978-0-321-53496-5 ..
• Langford, C. Dudley (1958), «Problem», Mathematical Gazette 42: 228 ..
• Nordh, Gustav (2008), «Perfect Skolem sets», Discrete Mathematics 308 (9): 1653-1664, MR 2392605, arXiv:math/0506155, doi:10.1016/j.disc.2006.12.003 ..
• Skolem, Thoralf (1957), «On certain distributions of integers in pairs with given differences», Mathematica Scandinavica 5: 57-68, MR 0092797 ..

Enlaces externos

• John E. Miller, Langford's Problem, 2006. (con una extensiva bibliografía).
• Weisstein, Eric W. «Langford's Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q3503249