Emparejamiento de Langford

En matemáticas combinatorias , un emparejamiento de Langford , también llamado secuencia de Langford , es una permutación de la secuencia de 2ⁿ números 1, 1, 2, 2, ..., n , n en la que los dos 1 están separados por una unidad, los dos 2 por dos unidades y, de forma más general, las dos copias de cada número k están separadas por k unidades. Los emparejamientos de Langford reciben su nombre de C. Dudley Langford, quien planteó el problema de su construcción en 1958.

El problema de Langford es la tarea de encontrar emparejamientos de Langford para un valor dado de n . ^{[ 1 ]}

El concepto estrechamente relacionado de secuencia de Skolem ^{[ 2 ]} se define de la misma manera, pero en su lugar permuta la secuencia 0, 0, 1, 1, ..., n − 1, n − 1.    

Un emparejamiento de Langford para n = 3 viene dado por la secuencia 2, 3, 1, 2, 1, 3.

Los emparejamientos de Langford existen solo cuando n es congruente con 0 o 3 módulo 4; por ejemplo, no hay emparejamiento de Langford cuando n = 1, 2 o 5.

Los números de emparejamientos de Langford diferentes para n = 1, 2, …, considerando cualquier secuencia como igual a su inversa, son:

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 2636337861200, 0, 0, … (secuencia A014552 en el OEIS ) .

Como describe Knuth (2008) , el problema de enumerar todos los emparejamientos de Langford para un n dado se puede resolver como una instancia del problema de cobertura exacta , pero para n grande el número de soluciones se puede calcular de manera más eficiente mediante métodos algebraicos.

Skolem (1957) utilizó secuencias de Skolem para construir sistemas triples de Steiner .

En la década de 1960, EJ Groth utilizó emparejamientos de Langford para construir circuitos para la multiplicación de enteros . ^{[ 3 ]}

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

• Gardner, Martin (1978), "El problema de Langford", Mathematical Magic Show , Vintage, pág.  70.
• Knuth, Donald E. (2008), El arte de la programación informática , Vol. IV, Fascículo 0: Introducción a los algoritmos combinatorios y las funciones booleanas, Addison-Wesley, ISBN 978-0-321-53496-5.
• Langford, C. Dudley (1958), "Problema", Mathematical Gazette , 42 (341): 228, doi : 10.2307/3610395 , JSTOR 3610395 .
• Nordh, Gustav (2008), "Conjuntos de Skolem perfectos", Matemáticas Discretas , 308 (9): 1653– 1664, arXiv : math/0506155 , doi : 10.1016/j.disc.2006.12.003 , MR 2392605 .
• Skolem, Thoralf (1957), "Sobre ciertas distribuciones de enteros en pares con diferencias dadas", Mathematica Scandinavica , 5 : 57–68 , doi : 10.7146/math.scand.a-10490 , MR 0092797 .

• John E. Miller, El problema de Langford , 2006. (con una extensa bibliografía ).
• Weisstein, Eric W. "El problema de Langford" . MundoMatemático .