Langfordské párování - Langford pairing

Langfordský pár pro n = 4.

v kombinační matematika, a Langfordské párování, také nazývaný a Langfordova sekvence, je permutace sekvence 2n čísla 1, 1, 2, 2, ..., n, n ve kterém jsou dvě 1s jedna jednotka od sebe, dvě 2s jsou dvě jednotky od sebe a obecněji dvě kopie každého čísla k jsou k jednotky od sebe. Langfordské dvojice jsou pojmenovány po C. Dudley Langfordovi, který v roce 1958 nastolil problém s jejich konstrukcí.

Langfordův problém je úkolem najít Langfordovy párování pro danou hodnotu n.[1]

Úzce související koncept a Skolemova sekvence[2] je definován stejným způsobem, ale místo toho permutuje sekvenci 0, 0, 1, 1, ..., n − 1, n − 1.

Příklad

Například spárování Langfordu pro n = 3 je dáno posloupností 2,3,1,2,1,3.

Vlastnosti

Langfordské párování existuje pouze tehdy, když n je shodný na 0 nebo 3 modulo 4; například neexistuje žádné Langfordské párování, když n = 1, 2 nebo 5.

Počet různých Langfordových párování pro n = 1, 2,…, počítajíc jakoukoli sekvenci jako stejnou jako její obrácení, jsou

0, 0, 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144,… (sekvence A014552 v OEIS ).

Tak jako Knuth (2008) popisuje problém se seznamem všech Langfordových párování pro daný n lze vyřešit jako instanci přesný problém s krytem, ale pro velké n počet řešení lze vypočítat efektivněji algebraickými metodami.

Aplikace

Skolem (1957) použili ke konstrukci sekvence Skolem Trojité systémy Steiner.

V 60. letech E. J. Groth použil Langfordovy párování ke konstrukci obvodů pro celé číslo násobení.[3]

Viz také

Poznámky

  1. ^ Knuth (2008); Gardner (1978).
  2. ^ Nordh (2008)
  3. ^ Knuth (2008).

Reference

  • Gardner, Martin (1978), „Langfordův problém“, Matematická magická show, Vintage, str. 70.
  • Knuth, Donald E. (2008), Umění počítačového programování, Sv. IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley, ISBN  978-0-321-53496-5.
  • Langford, C. Dudley (1958), „Problém“, Matematický věstník, 42: 228.
  • Nordh, Gustav (2008), „Perfect Skolem sets“, Diskrétní matematika, 308 (9): 1653–1664, arXiv:matematika / 0506155, doi:10.1016 / j.disc.2006.12.003, PAN  2392605.
  • Skolem, Thoralfe (1957), „O určitých distribucích celých čísel ve dvojicích s danými rozdíly“, Mathematica Scandinavica, 5: 57–68, PAN  0092797.

externí odkazy