Usuario:Dgallards/Taller

Emparejamiento de Langford para n = 4.

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

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

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

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

Véase también

• Permutacion 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 ..

Links externos

• 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]]