Quadrat llatí
Un Quadrat llatí és una matriu de n×n elements en la que cada cel·la està ocupada per un dels n símbols de tal manera que cadascun d'ells apareix exactament una vegada en cada columna i en cada fila de la matriu.
La següent matriu és un quadrat llatí:
| A | B | C |
| C | A | B |
| B | C | A |
Els quadrats llatins s'apliquen fonamentalment en el disseny d'experiments.
El nom de "quadrat llatí" deriva dels articles matemàtics de Leonhard Euler, qui va utilitzar caràcters llatins com a símbols.[1] Òbviament es poden utilitzar altres símbols en lloc de les lletres llatines. En l'exemple anterior, la seqüència alfabètica A, B, C pot ser substituïda per la seqüència de nombres enters 1, 2, 3.
Història
[modifica]El matemàtic coreà Choi Seok-jeong va ser el primer a publicar un exemple de quadrats llatins d'ordre nou, per construir un quadrat màgic el 1700, anterior, per tant, a Leonhard Euler en 67 anys.[2]
Terminologia
[modifica]Es diu que un quadrat llatí està reduït (o "normalitzat", o "en la forma estandarditzada") si la primera fila i la primera columna estan en el seu ordre natural. Per exemple, el primer quadrat podria estar reduït perquè la primera fila i la primera columna són A, B, C.
Permutant (reordenant) les fileres i columnes és possible construir un altre quadrat llatí. Així el quadrat:
| A | B | C |
| B | C | A |
| C | A | B |
és un quadrat llatí reduït, perquè tant la seva primera filera com la seva primera columna estan ordenades alfabèticament.
Propietats
[modifica]Representació del disseny ortogonal
[modifica]Si cada entrada d'un quadrat llatí n × n s'escriu com un triplet (f, c, s), on f és la fila, c la columna i s el símbol (en aquest cas un nombre en lloc de les lletres llatines), s'obtindran n² triplets, l'anomenat arranjament ortogonal del quadrat. Per exemple, per al primer quadrat llatí l'arranjament ortogonal serà:
{(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,3), (2,3,1), (3,1,3), (3,2,1), (3,3,2)}
- on, per exemple, el triplet (2,3,1) representa que el símbol a la fila 2 i la columna 3 és 1. La representació d'un quadrat llatí es pot escriure en termes de l'arranjament ortogonal, i queda com:
- hi ha n² tripletes de la forma (f, c, s), on 1 ≤ f, c, s ≤ n
- tots els parells (f, c) són diferents, tots els parells (f, s) són diferents, i tots els parells (c, s) també són diferents.
Per a qualsevol quadrat llatí, hi ha n² triplets però l'elecció de qualsevol de dos d'ells determina unívocament el tercer. (En cas contrari, un parell ordenat apareixeria més d'una vegada al quadrat llatí).
La representació com a arranjament ortogonal mostra que les files, columnes i símbols tenen un paper força similars, com s'aclarirà més endavant.
Classes equivalents de quadrats llatins
[modifica]Moltes de les operacions sobre un quadrat llatí produeixen un altre quadrat llatí (per exemple, girar-ho cap per avall).
Si permutem les files, les columnes, i els símbols d'un quadrat llatí, obtenim un nou quadrat llatí que s'anomena isotòpic al primer. L'isotopisme és una relació d'equivalència, de manera que el conjunt de tots els quadrats llatins es divideix en subconjunts anomenats classes d'isotopia, de tal manera que dos quadrats en la mateixa classe són isotòpics i dos en classes diferents no ho són.
Un altre tipus d'operació més fàcil d'explicar és l'ús de la representació com matriu ortogonal dels quadrats llatins. Si reordenem sistemàticament i coherent els tres punts en cada triplet (i per tant un altre quadrat llatí) s'obté una altra matriu ortogonal. Per exemple, podem reemplaçar cada triplet (f, c, s) per (c, f, s) que correspon a la transposició del quadrat (que es reflecteix sobre la seva diagonal principal), o podríem reemplaçar cada triplet (f, c, s) per (c, s, f), que és una operació més complicada. En total hi ha 6 possibilitats incloent la de "no fer res", donant-nos 6 quadrats llatins anomenats els conjugats del quadrat original.
Finalment, podem combinar aquestes dues operacions d'equivalència. Dos quadrats llatins es diu que són paratòpics si un d'ells és conjugat de l'altra. Això és de nou una relació d'equivalència, amb la classe d'equivalència principal anomenada classe principal, espècies, o classe paratòpica. Cada classe principal conté fins a 6 classes isotòpiques.
Nombre de quadrats llatins
[modifica]No es coneix una fórmula senzilla que permeti el càlcul del nombre Ln de quadrats llatins n × n per a n= 1,2, ..., n. Els límits superior i inferior més precisos coneguts fins ara per a n gran estan molt separats. Un resultat clàssic acceptat és:[3]
El 1992 es va publicar una fórmula senzilla i explícita per al nombre de quadrats llatins, però encara a hores d'ara no és fàcilment computable a causa de l'augment exponencial en el nombre de termes. Aquesta fórmula per al nombre Ln de n × n quadrats llatins és:[4]
on Bn és el conjunt de totes les matrius {0,1} n × n, σ0(A) és el nombre d'entrades iguals a zero de la matriu A, i per(A) és el permanent de la matriu A.
La taula següent conté tots els valors exactes coneguts. Es pot observar que els nombres creixen molt ràpidament. Per a cada n, el nombre total de quadrats llatins disponibles (seqüència A002860 a OEIS) és n! (n-1)! vegades el nombre de quadrats llatins reduïts (seqüència A000315 a OEIS).
| n | Quadrats llatins reduïts n | Nombre total de quadrats llatins n |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 12 |
| 4 | 4 | 576 |
| 5 | 56 | 161280 |
| 6 | 9408 | 812851200 |
| 7 | 16942080 | 61479419904000 |
| 8 | 535281401856 | 108776032459082956800 |
| 9 | 377597570964258816 | 5524751496156892842531225600 |
| 10 | 7580721483160132811489280 | 9982437658213039871725064756920320000 |
| 11 | 5363937773277371298119673540771840 | 776966836171770144107444346734230682311065600000 |
Per a cada n, cada classe isotòpica (seqüència A040082 en OEIS) conté fins (n!) 3 quadrats llatins (el nombre exacte varia), mentre que cada classe principal (seqüència A003090 en OEIS) conté 1, 2, 3 o 6 classes isotopiques.
| n | classes principals | classes isotòpiques |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 4 | 2 | 2 |
| 5 | 2 | 2 |
| 6 | 12 | 22 |
| 7 | 147 | 564 |
| 8 | 283657 | 1676267 |
| 9 | 19270853541 | 115618721533 |
| 10 | 34817397894749939 | 208904371354363006 |
| 11 | 2036029552582883134196099 | 12216177315369229261482540 |
Algorismes
[modifica]Per a petits quadrats és possible generar permutacions i comprovar si es compleixen les propietats dels quadrats llatins. Per a quadrats més grans, l'algorisme de Jacobson i Matthews permet el mostreig d'una distribució uniforme en l'espai de n × n quadrats llatins.[5]
Aplicacions
[modifica]Disseny d'experiments
[modifica]
En el disseny d'experiments, els quadrats llatins són un cas especial de dissenys en files i columnes amb dos factors de bloqueig.[6][7] Molts d'aquests dissenys en files i columnes es construeixen precisament mitjançant la concatenació de quadrats llatins.[8][9][10][11][12]
Tot i que es té consciència de la utilització dels quadrats llatins en estudis agrícoles a França durant el segle xix, no és fins a 1926 que es popularitzen com dissenys d'experiències després dels treballs de R. A. Fisher.
Al bosc de Bettgelert (Gal·les), Fisher va estudiar el creixement de certes coníferes en funció de l'altura del terreny, l'exposició al vent i el sol i el tipus de conífera (L'estudi es va iniciar el 1926, es va publicar en 1929 i va finalitzar el 1966).
El factor "en files" correspon a l'alçada del terreny, les "columnes" a l'exposició al vent i al sol i el tercer factor a les següents coníferes:
A: Picea de Sitka (Picea sitchensis)
B: Làrix japonès
C: Picea de Sitka / Làrix japonès 50/50
D: Picea de Sitka / Pinus contorta 50/50
E: Picea de Noruega / Làrix europeu 50/50
Un cop definida la variable resposta i realitzats els experiments es poden analitzar els resultats mitjançant una anàlisi de variància de tres factors (files, columnes i lletres llatines).[13][14]
Trencaclosques matemàtics
[modifica]El popular trencaclosques Sudoku és un cas especial de quadrat llatí, ja que tota solució d'un sudoku és un quadrat llatí. Un sudoku imposa però una restricció addicional als subgrups de 3 × 3, aquests només han de contenir els dígits de l'1 al 9 (en la versió estàndard).
Referències
[modifica]- ↑ Wallis, W.D.; George, J. C. Introduction to Combinatorics. Boca Raton (FL): CRC Press, 2011. ISBN 978-1-4398-0623-4.
- ↑ Colbourn, Charles J.; Dinitz, Jeffrey H. Handbook of Combinatorial Designs (en anglès). 2a. CRC Press, 2006, p. 12. ISBN 9781420010541.
- ↑ Van Lin, J. H.; Wilson, R. M. A Course in Combinatorics. 2nd Ed.. ambridge: Cambridge University Press, 1992. ISBN 978-0-521-00601-9.
- ↑ Jia-yu, S.; Wan-di, W «A formula for the number of Latin squares». Discrete Mathematics, 1992, pàg. 293-296. DOI: 10.1016/0012-365X(92)90722-R.
- ↑ Jacobson, M. T.; Matthews, P «Generating uniformly distributed random latin squares». Journal of Combinatorial Designs, 4, (6), 1996, pàg. 405 - 437. DOI: 10.1002/(sici)1520-6610(1996)4:6<405::aid-jcd3>3.0.co;2-j.
- ↑ Bailey, R.A. 6 Row-Column designs and 9 More about Latin squares. Design of Comparative Experiments. Cambridge: Cambridge University Press, 2008. ISBN 978-0-521-68357-9.
- ↑ Hinkelmann, K.; Kempthorne, O. Design and Analysis of Experiments.. Vol. I i II. 2nd Ed. Hoboken: John Wiley & Sons, Inc.. ISBN 978-0-470-38551-7.
- ↑ Raghavarao, D. Constructions and Combinatorial Problems in Design of Experiments. New York (NY): Dover Pub., 1988. ISBN 0-486-65685-3.
- ↑ Raghavarao, D. Block Designs: Analysis, Combinatorics and Applications. Singapore: World Scientific Publishing Co., 2005. ISBN 981-256-360-1.
- ↑ Shah, K. R.; Sinha, B. K. 4 Row-Column Designs. Theory of Optimal Designs. Berlin: Springer-Verlag, 1989 (Lecture Notes in Statistics. 54). ISBN 0-387-96991-8.
- ↑ Shah, K. R.; Sinha, B. K. «Row-column designs». A: S. Ghosh, C. R. Rao. Design and analysis of experiments. Handbook of Statistics .. 13. Amsterdam: North-Holland Publishing Co, 1996. ISBN 0-444-82061-2.
- ↑ Street, A. P.; Sinha, B. K. Combinatorics of Experimental Design. New York (NY): Oxford University Press., 1987. ISBN 0-19-853256-3.
- ↑ Box, G. E. P.; Hunter, W. G.; Hunter, J. S. Estadística para Investigadores. 1ª Ed.. Barcelona: Editorial Reverte, 1994. ISBN 978-8429150414.
- ↑ Box, G. E. P.; Hunter, J. S.; Hunter, W. G. Estadística per a científics i tècnics: disseny d'experiments i innovació. 2ª Ed. Barcelona: Editorial Reverté, 2008. ISBN 978-84-291-5170-1.
Vegeu també
[modifica]Enllaços externs
[modifica]
- Weisstein,Eric W., "Latin Square", a MathWorld
- Latin Squares. a Encyclopaedia of Mathematics
| Tipus |  | |
|---|---|---|
| Formes relacionades | ||
| Formes dimensionals superiors | ||
| Conceptes | ||
| Conceptes relacionats |
| |
| Vegeu també | ||
