Langfordské párování - Langford pairing
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
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é
- Stirlingova permutace , jiný typ permutace stejné multisetu
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
- John E. Miller, Langfordův problém , 2006. (s rozsáhlou bibliografií ).
- Weisstein, Eric W. „Langfordův problém“ . MathWorld .