Langfordské párování - Langford pairing

Langfordovo párování pro n = 4.

V kombinatorické matematice je Langfordovo párování , nazývané také Langfordova posloupnost , permutací posloupnosti 2 n čísel 1, 1, 2, 2, ..., n , n, ve kterých 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 představil problém s jejich konstrukcí.

Langfordovým problémem je úkol najít Langfordovy párování pro danou hodnotu n .

Úzce související koncept sekvence Skolem 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 Langfordovo párování pro n = 3 je dáno posloupností 2,3,1,2,1,3.

Vlastnosti

Langfordské párování existuje pouze v případě, že n je shodné s 0 nebo 3 modulo 4; například neexistuje žádné Langfordovo párování, když n = 1, 2 nebo 5.

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

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

Jak popisuje Knuth (2008) , problém výpisu všech Langfordových párů pro dané n lze vyřešit jako instanci přesného krycího problému , ale u velkých n lze počet řešení efektivněji vypočítat algebraickými metodami.

Aplikace

Skolem (1957) použil Skolemovy sekvence ke konstrukci Steinerových trojitých systémů .

V 60. letech použil EJ Groth Langfordovy párování ke konstrukci obvodů pro celočíselné násobení .

Viz také

Poznámky

Reference

  • Gardner, Martin (1978), „Langfordův problém“, Mathematical Magic Show , Vintage, str. 70.
  • Knuth, Donald E. (2008), The Art of Computer Programming , sv. 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“, Diskrétní matematika , 308 (9): 1653–1664, arXiv : math / 0506155 , doi : 10,1016 / j.disc.2006.12.003 , MR  2392605.
  • Skolem, Thoralf (1957), „O určitých distribucích celých čísel v párech s danými rozdíly“, Mathematica Scandinavica , 5 : 57–68, MR  0092797.

externí odkazy