Emparelhamento de Langford

Na matemática combinatória, o emparelhamento de Langford, também chamado de sequência de Langford , é uma permutação da seqüência de 2n números 1, 1, 2, 2, ..., n , n , em que os uns são uma unidade a parte, os dois são duas unidades a parte, e de um modo geral, as duas cópias de cada número k são k unidades a parte. O emparelhamento de Langford foi nomeado depois de C. Dudley Langford, que pôs o problema de construção em 1958.

A Langford pairing for n = 4.

O problema de Langford é a tarefa de encontrar pares de Langford para um dado valor de n.

A forte relação do conceito de uma sequência de Skolem é definida da mesma maneira, mas permutando 0, 0, 1, 1, ..., n  − 1, n − 1.

Exemplo

Por exemplo, um emparelhamento de Langford por n = 3 é dada pela sequência 2,3,1,2,1,3.

Propriedades

Os emparelhamentos de Langford só existem quando n é congruente a 0 ou 3 módulo 4; por exemplo, não há pareamento de Langford quando n = 1, 2, ou 5.

Os números de diferentes emparelhamentos de Langford para n = 1, 2, ..., contando qualquer sequência como sendo a mesma que a sua inversa, são os seguintes: 0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, ...

Como Knuth (2008) descreve, o problema da listagem de todos os emparelhamentos de Langford para um determinado n pode ser resolvido como uma instância de problema da cobertura exata, mas para grandes n o número de soluções pode ser calculado de forma mais eficiente através de métodos algébricos.

Aplicações

Skolem (1957) usou sequências de Skolem para construir sistema triplo de Steiner.

Em 1960s, E. J. Groth utilizou emparelhamento de Langford para construir circuitos para multiplicação de inteiros.

Ver também

• Permutação de Stirling, um tipo diferente de permutação do mesmo multiconjunto

Referências

• Gardner, Martin (1978), «Langford's problem», Mathematical Magic Show, Vintage, p. 70 .
• Knuth, Donald E. (2008), The Art of Computer Programming, ISBN 978-0-321-53496-5, Vol. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley .
• 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 .

Ligações externas

• John E. Miller, Langford's Problem, 2006. (with an extensive bibliography).
• Weisstein, Eric W. «Langford's Problem» (em inglês). MathWorld