Persegi Latin
Dalam kombinatorika dan rancangan percobaan, persegi Latin adalah persegi berukuran n × n yang berisi n simbol berbeda, masing-masing hanya muncul sekali pada setiap kolom dan pada setiap baris. Contoh dari persegi Latin 3×3 adalah
A | B | C |
C | A | B |
B | C | A |
Istilah "persegi Latin" terinspirasi oleh makalah matematika oleh Leonhard Euler (1707–1783), yang menggunakan alfabet Latin sebagai simbol.[2] Sembarang himpunan simbol dapat digunakan untuk membuat persegi ini: pada contoh di atas, alfabet A, B, C dapat diganti dengan barisan bilangan bulat 1, 2, 3.
Sejarah
[sunting | sunting sumber]Matematikawan Korea Choi Seok-jeong pertama kali menerbitkan sebuah contoh persegi Latin berukuran 9×9, dalam upayanya membuat persegi ajaib pada tahun 1700; lebih awal 67 daripada Leonhard Euler.[3]
Bentuk tereduksi
[sunting | sunting sumber]Persegi Latin dikatakan tereduksi (juga ternormalkan atau dalam bentuk standar) jika urutan simbol pada baris pertama dan kolom pertama sama dengan urutan aslinya.[4] Sebagai contoh, persegi Latin pada contoh di atas tidak tereduksi karena kolom pertamanya adalah A, C, B, bukan A, B, C.
Semua persegi Latin dapat direduksi dengan mempermutasi (yakni, menyusun ulang) urutan kolom dan baris. Pada persegi di atas, menukar baris kedua dengan baris ketiga akan menghasilkan persegi Latin:
A | B | C |
B | C | A |
C | A | B |
Persegi Latin ini tereduksi; urutan simbol pada baris pertama dan kolom pertamanya sama dengan urutan alfabet A, B, C.
Sifat
[sunting | sunting sumber]Representasi larik ortogonal
[sunting | sunting sumber]Persegi Latin dapat disajikan dalam bentuk himpunan, disebut dengan larik ortogonal, dengan membuat tripel untuk setiap elemen di persegi Latin. Pada tripel ini, menyatakan urutan baris, menyatakan urutan kolom, dan menyatakan simbol pada baris ke- dan kolom ke-. Sebagai contoh, representasi larik ortogonal dari persegi Latin
1 | 2 | 3 |
2 | 3 | 1 |
3 | 1 | 2 |
adalah {(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) }. Larik ortogonal umumnya ditulis dalam bentuk tabel, dengan setiap baris berisi nilai-nilai tripel, sebagai contoh:
r | c | s |
---|---|---|
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 |
Persegi Latin dapat didefinisikan dengan menggunakan larik ortogonal:
persegi Latin adalah himpunan dari tripel , dengan , dan memenuhi: setiap pasangan berurut bernilai unik, setiap pasangan bernilai unik, dan setiap pasangan bernilai unik.
Banyak persegi Latin
[sunting | sunting sumber]Tidak ada rumus sederhana untuk menghitung nilai , yakni banyaknya persegi Latin berukuran berisi simbol-simbol . Nilai batas atas dan batas bawah terbaik untuk memiliki jarak yang besar. Salah satu hasil[5] menyatakan bahwaSebuah rumus eksplisit dan sederhana untuk banyak persegi Latin diterbitkan pada tahun 1992, namun sulit untuk dihitung karena banyak suku yang bertambah secara eksponensial. Rumus ini menyatakan banyaknya persegi Latin berukuran n × n adalahdengan Bn menyatakan himpunan semua matriks binear berukuran n × n, menyatakan banyak elemen nol di matriks , dan adalah permanen dari matriks .[6]
Catatan kaki
[sunting | sunting sumber]- ^ Busby, Mattha (27 June 2020). "Cambridge college to remove window commemorating eugenicist". The Guardian. Diakses tanggal 2020-06-28.
- ^ Wallis, W. D.; George, J. C. (2011), Introduction to Combinatorics, CRC Press, hlm. 212, ISBN 978-1-4398-0623-4
- ^ Colbourn, Charles J.; Dinitz, Jeffrey H. (2 November 2006). Handbook of Combinatorial Designs (dalam bahasa Inggris) (edisi ke-2nd). CRC Press. hlm. 12. ISBN 9781420010541. Diakses tanggal 28 March 2017.
- ^ Dénes & Keedwell 1974, p. 128
- ^ van Lint & Wilson 1992, pp. 161-162
- ^ Jia-yu Shao; Wan-di Wei (1992). "A formula for the number of Latin squares". Discrete Mathematics. 110 (1–3): 293–296. doi:10.1016/0012-365x(92)90722-r .
Referensi
[sunting | sunting sumber]- Bailey, R.A. (2008). "6 Row-Column designs and 9 More about Latin squares". Design of Comparative Experiments. Cambridge University Press. ISBN 978-0-521-68357-9. MR 2422352.
- Dénes, J.; Keedwell, A. D. (1974). Latin squares and their applications. New York-London: Academic Press. hlm. 547. ISBN 0-12-209350-X. MR 0351850.
- Shah, Kirti R.; Sinha, Bikas K. (1989). "4 Row-Column Designs". Theory of Optimal Designs. Lecture Notes in Statistics. 54. Springer-Verlag. hlm. 66–84. ISBN 0-387-96991-8. MR 1016151.
- van Lint, J. H.; Wilson, R. M. (1992). A Course in Combinatorics. Cambridge University Press. hlm. 157. ISBN 0-521-42260-4.
Bacaan lebih lanjut
[sunting | sunting sumber]- Dénes, J. H.; Keedwell, A. D. (1991). Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics. 46. Paul Erdős (foreword). Amsterdam: Academic Press. ISBN 0-444-88899-3. MR 1096296.
- Hinkelmann, Klaus; Kempthorne, Oscar (2008). Design and Analysis of Experiments. I, II (edisi ke-Second). Wiley. ISBN 978-0-470-38551-7. MR 2363107.
- Hinkelmann, Klaus; Kempthorne, Oscar (2008). Design and Analysis of Experiments, Volume I: Introduction to Experimental Design (edisi ke-Second). Wiley. ISBN 978-0-471-72756-9. MR 2363107.
- Hinkelmann, Klaus; Kempthorne, Oscar (2005). Design and Analysis of Experiments, Volume 2: Advanced Experimental Design (edisi ke-First). Wiley. ISBN 978-0-471-55177-5. MR 2129060.
- Knuth, Donald (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-03804-0.
- Laywine, Charles F.; Mullen, Gary L. (1998). Discrete mathematics using Latin squares. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons, Inc. ISBN 0-471-24064-8. MR 1644242.
- Shah, K. R.; Sinha, Bikas K. (1996). "Row-column designs". Dalam S. Ghosh and C. R. Rao. Design and analysis of experiments. Handbook of Statistics. 13. Amsterdam: North-Holland Publishing Co. hlm. 903–937. ISBN 0-444-82061-2. MR 1492586.
- Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (edisi ke-corrected reprint of the 1971 Wiley). New York: Dover. ISBN 0-486-65685-3. MR 1102899.
- Street, Anne Penfold; Street, Deborah J. (1987). Combinatorics of Experimental Design. New York: Oxford University Press. ISBN 0-19-853256-3. MR 0908490.
- Berger, Paul D.; Maurer, Robert E.; Celli, Giovana B. (November 28, 2017). Experimental Design with Applications in Management, Engineering, and the Sciences (edisi ke-2nd edition (November 28, 2017)). Springer. hlm. 267–282.