Langford parning

En Langford-parning för n = 4.

I kombinatorisk matematik är en Langford-parning , även kallad en Langford-sekvens , en permutation av sekvensen av 2 n nummer 1, 1, 2, 2, ..., n , n där de två 1:orna är en enhet ifrån varandra, två 2:or är två enheter från varandra, och mer generellt är de två kopiorna av varje nummer k k enheter från varandra. Langford-par är uppkallade efter C. Dudley Langford, som ställde upp problemet med att konstruera dem 1958.

Langfords problem är uppgiften att hitta Langford-parningar för ett givet värde på n .

Det närbesläktade konceptet för en Skolem-sekvens definieras på samma sätt, men permuterar istället sekvensen 0, 0, 1, 1, ..., n − 1, n − 1.

Exempel

En Langford-parning för n = 3 ges av sekvensen 2, 3, 1, 2, 1, 3.

Egenskaper

Langford-parningar existerar endast när n är kongruent med 0 eller 3 modulo 4; till exempel finns det ingen Langford-parning när n = 1, 2 eller 5.

Antalet olika Langford-par för n = 1, 2, …, räknar vilken sekvens som helst som densamma som dess omkastning, är

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, 0, 0, 39809640, 326721800, 0, 0, 256814891280, 6,02, 6,02 014552 i OEIS ).

Som Knuth (2008) beskriver kan problemet med att lista alla Langford-parningar för ett givet n lösas som en instans av det exakta täckningsproblemet, men för stora n kan antalet lösningar beräknas mer effektivt med algebraiska metoder.

Ansökningar

Skolem (1957) använde Skolem-sekvenser för att konstruera Steiners trippelsystem .

På 1960-talet använde EJ Groth Langford-parningar för att konstruera kretsar för heltalsmultiplikation .

Se även

• Stirling permutation , en annan typ av permutation av samma multiset

Anteckningar

• Gardner, Martin (1978), "Langfords problem", Mathematical Magic Show , Vintage, sid. 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, arXiv : math/0506155 , doi : 10.1016/j.disc.2006.12.003 , 39260 39 .
•   Skolem, Thoralf (1957), "Om vissa fördelningar av heltal i par med givna skillnader", Mathematica Scandinavica , 5 : 57–68, MR 0092797 .

externa länkar

• John E. Miller, Langford's Problem , 2006. (med en omfattande bibliografi ).
• Weisstein, Eric W. "Langfords problem" . MathWorld .