Latinsk rektangel
I kombinatorisk matematik är en latinsk rektangel en r × n matris (där r ≤ n ), som använder n symboler, vanligtvis siffrorna 1, 2, 3, ..., n eller 0, 1, ..., n − 1 som dess poster, utan att något nummer förekommer mer än en gång i någon rad eller kolumn.
En n × n latinsk rektangel kallas en latinsk kvadrat .
Ett exempel på en 3 × 5 latinsk rektangel är:
0 1 2 3 4 3 4 0 1 2 4 0 3 2 1
Normalisering
En latinsk rektangel kallas normaliserad (eller reducerad ) om dess första rad är i naturlig ordning och så även dess första kolumn.
Exemplet ovan är inte normaliserat.
Uppräkning
Låt L ( k, n ) beteckna antalet normaliserade k × n latinska rektanglar. Då är det totala antalet k × n latinska rektanglar
En 2 × n latinsk rektangel motsvarar en permutation utan fasta punkter . Sådana permutationer har kallats diskordanta permutationer . En uppräkning av permutationer som inte överensstämmer med en given permutation är det berömda problème des rencontres . Uppräkningen av permutationer som inte överensstämmer med två permutationer, varav den ena är en enkel cyklisk förskjutning av den andra, är känd som det reducerade problème des ménages .
Antalet normaliserade latinska rektanglar, L ( k , n ) , av små storlekar ges av
k\n 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 1 1 3 11 53 309 2119 3 1 4 46 1064 35792 1673792 4 4 56 6552 1293216 420909504 5 56 9408 11270400 27206658048 6 9408 16942080 335390189568 7 16942080 535281401856 8 535281401856
När k = 1, det vill säga, det finns bara en rad, eftersom de latinska rektanglarna är normaliserade finns det inget val för vad denna rad kan vara. Tabellen visar också att L ( n − 1, n ) = L ( n , n ) , vilket följer eftersom om endast en rad saknas kan den saknade posten i varje kolumn bestämmas från den latinska kvadrategenskapen och rektangeln kan vara unikt utökat till ett latinskt torg.
Utdragbarhet
Egenskapen att kunna förlänga en latinsk rektangel som saknas en rad till en latinsk kvadrat som nämnts ovan, kan förstärkas avsevärt. Nämligen, om r < n , så är det möjligt att lägga till n − r rader till en r × n latinsk rektangel för att bilda en latinsk kvadrat, med hjälp av Halls äktenskapssats .
Semi-latinska rutor
En semi-latinsk kvadrat är en annan typ av ofullständig latinsk kvadrat. En semi-latinsk kvadrat är en n × n array, L , där vissa positioner är obesatta och andra positioner är upptagna av ett av heltalen { 0, 1, ..., n − 1 }, så att om ett heltal k förekommer i L , sedan förekommer det n gånger och inga två k: n hör till samma rad eller kolumn. Om m olika heltal förekommer i L , då L har index m .
Till exempel är en semi-latinsk kvadrat av ordning 5 och index 3:
1 0 2 2 1 0 0 1 2 2 0 1 2 0 1
En semi-latinsk kvadrat av ordningen n och index m kommer att ha nm fyllda positioner. Frågan uppstår, kan en halvlatinsk ruta kompletteras till en latinsk ruta? Något överraskande är svaret alltid.
Låt L vara en halvlatinsk kvadrat av ordningen n och index m , där m < n . Sedan L kompletteras till en latinsk ruta.
Ett sätt att bevisa detta är att observera att en semi-latinsk kvadrat av ordningen n och index m är ekvivalent med en m × n latinsk rektangel. Låt L = || a ij || vara en latinsk rektangel och S = || b ij || vara en halvlatinsk kvadrat, då ges ekvivalensen av
Till exempel den latinska rektangeln 3×5
0 1 2 3 4 3 4 1 0 2 1 0 4 2 3
motsvarar denna halvlatinska kvadrat av ordning 5 och index 3:
0 2 1 2 0 1 0 2 1 1 0 2 1 2 0
eftersom till exempel a 10 = 3 i den latinska rektangeln så b 30 = 1 i den halvlatinska kvadraten.
Ansökningar
Inom statistiken har latinska rektanglar tillämpningar vid design av experiment .
Se även
Anteckningar
- Brualdi, Richard A. (2010), Introductory Combinatorics (5:e upplagan), Prentice Hall, ISBN 978-0-13-602040-0
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
- Dénes, J.; Keedwell, AD (1974), Latin squares and their applications , New York-London: Academic Press, sid. 547, ISBN 0-12-209350-X , MR 0351850
Vidare läsning
- Mirsky, L. (1971), Transversal theory: en redogörelse för några aspekter av kombinatorisk matematik , Academic Press, ISBN 0-12-498550-5 , OCLC 816921720
- Riordan, John (2002) [1958], Introduction to Combinatorial Analysis , Dover, ISBN 978-0-486-42536-8
externa länkar
- Weisstein, Eric W., "Latin Rectangle" , mathworld.wolfram.com , hämtad 2020-07-12