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.
O problema de Langford é a tarefa de encontrar pares de Langford para um dado valor de n.[1]
A forte relação do conceito de uma sequência de Skolem [2] é definida da mesma maneira, mas permutando 0, 0, 1, 1, ..., n − 1, n − 1.
Exemplo[editar | editar código-fonte]
Por exemplo, um emparelhamento de Langford por n = 3 é dada pela sequência 2,3,1,2,1,3.
Propriedades[editar | editar código-fonte]
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[editar | editar código-fonte]
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.[3]
Ver também[editar | editar código-fonte]
- Permutação de Stirling, um tipo diferente de permutação do mesmo multiconjunto
Notas[editar | editar código-fonte]
Referências[editar | editar código-fonte]
- 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[editar | editar código-fonte]
- John E. Miller, Langford's Problem, 2006. (with an extensive bibliography).
- Weisstein, Eric W. «Langford's Problem» (em inglês). MathWorld