Emparejamiento de Langford

Emparejamiento de Langford per a n = 4.

En combinatòria matemàtica, un Emparejamiento de Langford, també cridada seqüència de Langford, és una permutació de la seqüència de 2 números n 1, 1, 2, 2, ..., n, n en la qual els dos uns estan una unitat separats, els dos doses estan separats dos unitats, i d'una forma més general dos còpies de cada número k estan separades k unitats. Els emparejamientos de Langford es diuen aixina gràcies a C. Dudley Langford, el qual va formular el problema de la seua construcció en 1958.

El problema de Langford descriu la tasca de trobar emparejamientos de Langford per a un valor n.

El concepte altament relacionat, seqüència Skolem, es definix de la mateixa forma, pero esta permuta la seqüència 0, 0, 1, 1, ..., n - 1, n - 1.

Eixemple

Per eixemple, un emparejamiento de Langford per a n = 3 mostra la seqüència: 2,3,1,2,1,3.

Propietats

Els emparejamientos de Lanford solament existixen quan n és congruent a 0 o 3 mòdul de 4; per eixemple, no hi ha emparejamiento de Langford quan n = 1, 2, o 5.

Els números per als diferents emparejamientos de Langford per a n = 1, 2, …, contant qualsevol seqüència com si fora la mateixa que en invertir-la, són

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, … Plantilla:OEIS.

Com descriu Knuth (2008), el problema de llistar tots els emparejamientos de Langford per a un n donat pot ser resolt com un cas del problema de la cobertura exacta, pero per a un n més gran, el número de solucions pot ser calculada més eficientemente en métodos algebraics.

Vore també

• Permutació de Stirling, un tipo diferent de permutació del mateix multiconjunto

Referències

• .
• .
• .
• .
• .