Usuario:Dgallards/Taller
En combinatoria matemática, un Emparejamiento de Langford, tambien 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 mas 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 Lanfords solo existen cuando n es congruente a 0 o 3 modulo 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 de el problema de la cobertura exacta, pero para un n mas grande, el número de soluciones puede ser calculada mas 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 to construir circuitos para la multiplicación de enteros.[3]
Véase también[editar]
- Permutacion 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..
Links externos[editar]
- John E. Miller, Langford's Problem, 2006. (with an extensive bibliography).
- Weisstein, Eric W. «Langford's Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
[[Category:Combinatoria]]