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.
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
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
- Permutación de Stirling, un tipo diferente de permutación del mismo multiconjunto
Notas editar
Referencias editar
- 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 editar
- 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.
- Esta obra contiene una traducción total derivada de «Langford pairing» de Wikipedia en inglés, concretamente de esta versión del 29 de octubre de 2014, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
Datos: Q3503249
