Latin kare - Latin square

7 × 7 Latin karenin görüntülenmesi, bu vitray pencere onur Ronald Fisher, kimin Deney Tasarımı Latin kareleri tartışıldı.

İçinde kombinatorik ve deneysel tasarım, bir Latin kare birn × n dolu dizin her biri tam olarak her satırda bir kez ve her sütunda tam olarak bir kez yer alan farklı semboller. 3 × 3 Latin kareye bir örnek:

"Latin kare" adı, matematiksel makalelerden esinlenmiştir. Leonhard Euler (1707–1783), kullananlar Latin sembolleri semboller olarak^[1] ancak herhangi bir sembol seti kullanılabilir: yukarıdaki örnekte, alfabetik sıra A, B, C ile değiştirilebilir tamsayı dizisi 1, 2, 3. Euler genel Latin kareleri teorisine başladı.

Tarih

Koreli matematikçi Choi Seok-jeong bir oluşturmak için dokuzuncu mertebeden Latin karelerinin bir örneğini yayınlayan ilk kişiydi. sihirli kare 1700'de Leonhard Euler'den 67 yıl önce.^[2]

Küçültülmüş form

Latin kare olduğu söyleniyor indirgenmiş (Ayrıca, normalleştirilmiş veya standart biçimde) hem ilk satırı hem de ilk sütunu doğal sıralarındaysa.^[3] Örneğin, yukarıdaki Latin kare indirgenmez çünkü ilk sütunu A, B, C yerine A, C, B'dir.

Herhangi bir Latin kare küçültülebilir permütasyon (yani, satırları ve sütunları yeniden sıralamak). Burada yukarıdaki matrisin ikinci ve üçüncü satırlarını değiştirmek aşağıdaki kareyi verir:

Bu Latin kare küçültülmüştür; hem ilk satırı hem de ilk sütunu alfabetik olarak sıralanmıştır A, B, C.

Özellikleri

Ortogonal dizi gösterimi

Her giriş bir n × n Latin kare üçlü olarak yazılır (r,c,s), nerede r sıra c sütun ve s semboldür, bir dizi elde ederiz n² üçlü aradı ortogonal dizi karenin gösterimi. Örneğin, Latin karenin ortogonal dizi gösterimi

dır-dir

{ (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) },

burada örneğin üçlü (2, 3, 1) 2. satırda ve 3. sütunda 1. sembol olduğu anlamına gelir. Ortogonal diziler genellikle üçlülerin satırlar olduğu dizi biçiminde yazılır, örneğin:

Latin karenin tanımı, ortogonal diziler cinsinden yazılabilir:

• Latin kare bir dizi n² üçlü (r, c, s), burada 1 ≤ r, c, s ≤ n, öyle ki tüm sıralı çiftler (r, c) farklıdır, tüm sıralı çiftler (r, s) farklıdır ve tüm sıralı çiftler (c, s) farklıdır.

Bu şu demektir n² sıralı çiftler (r, c) tüm çiftlerdir (ben, j) 1 ≤ ile ben, j ≤ n, her biri bir kez. Aynısı sıralı çiftler için de geçerlidir (r, s) ve sıralı çiftler (c, s).

Ortogonal dizi gösterimi, aşağıda açıklanacağı gibi satırların, sütunların ve sembollerin oldukça benzer roller oynadığını gösterir.

Latin karelerinin eşdeğerlik sınıfları

Bir Latin karesindeki birçok işlem başka bir Latin karesi oluşturur (örneğin, onu ters çevirmek).

Satırları değiştirirsek, sütunları değiştirirsek ve bir Latin karesinin sembollerinin isimlerini değiştirirsek, olduğu söylenen yeni bir Latin kare elde ederiz. izotopik ilkine. İzotopizm bir denklik ilişkisi, bu nedenle tüm Latin kareler kümesi, adı verilen alt kümelere bölünür izotopi sınıfları, öyle ki aynı sınıftaki iki kare izotopik ve farklı sınıflardaki iki kare izotopik değil.

Latin karenin ortogonal dizi gösterimini kullanarak açıklamak için en kolay işlem türü başka bir işlemdir. Her üçlüdeki üç öğeyi sistematik ve tutarlı bir şekilde yeniden sıralarsak (yani, dizi biçimindeki üç sütuna izin verirsek), başka bir ortogonal dizi (ve böylece başka bir Latin kare) elde edilir. Örneğin, her üçlüyü (r,c,s) tarafından (c,r,s) karenin transpoze edilmesine karşılık gelir (ana köşegenini yansıtır) veya her üçlüyü değiştirebiliriz (r,c,s) tarafından (c,s,r), daha karmaşık bir işlemdir. "Hiçbir şey yapma" da dahil olmak üzere toplamda 6 olasılık vardır ve bize eşlenik adı verilen 6 Latin karesi verir (ayrıca felaketler ) orijinal karenin.^[4]

Son olarak, bu iki denklik işlemini birleştirebiliriz: iki Latin karesinin olduğu söylenir paratopik, Ayrıca ana sınıf izotopik, biri diğerinin eşleniğine izotopik ise. Bu yine bir eşdeğerlik ilişkisidir, eşdeğerlik sınıfları ana sınıflar, Türlerveya paratopi sınıfları.^[4] Her ana sınıf, altı adede kadar izotopi sınıfı içerir.

Numara

Sayı için kolayca hesaplanabilen bilinen bir formül yoktur L_n nın-nin n × n Sembollerle Latin kareler 1,2,...,n. Büyük olduğu bilinen en doğru üst ve alt sınırlar n çok uzak. Klasik bir sonuç^[5] bu mu

${displaystyle prod _ {k = 1} ^ {n} left (k! ight) ^ {n / k} geq L_ {n} geq {frac {left (n! ight) ^ {2n}} {n ^ {n ^ {2}}}}.}$

Latin karelerinin sayısı için basit ve açık bir formül 1992'de yayınlandı, ancak terimlerin sayısındaki üstel artış nedeniyle hala kolayca hesaplanamıyor. Sayı için bu formül L_n nın-nin n × n Latin kareler

${displaystyle L_ {n} = n! sum _ {Ain B_ {n}} ^ {} (- 1) ^ {sigma _ {0} (A)} {inom {operatöradı {per} A} {n}}, }$

nerede B_n hepsinin setidir n × n {0, 1} matrisler, σ₀(Bir) matristeki sıfır girişlerin sayısıdır Bir, ve başına(Bir) ... kalıcı matrisin Bir.^[6]

Aşağıdaki tablo bilinen tüm kesin değerleri içermektedir. Rakamların son derece hızlı arttığı görülmektedir. Her biri için nLatin karelerinin toplam sayısı (dizi A002860 içinde OEIS ) dır-dir n! (n-1)! indirgenmiş Latin karelerinin sayısının (sıra A000315 içinde OEIS ).

Her biri için n, her bir izotopi sınıfı (dizi A040082 içinde OEIS ) kadar içerir (n!)³ Latin kareler (tam sayı değişir), her ana sınıf (sıra A003090 içinde OEIS ) 1, 2, 3 veya 6 izotopi sınıfı içerir.

Yapısal olarak farklı Latin karelerinin sayısı (yani kareler, sembollerin dönüşü, yansıması ve / veya permütasyonu yoluyla özdeş hale getirilemez) n = 1'den 7'ye kadar sırasıyla 1, 1, 1, 12, 192, 145164, 1524901344'tür (sıra A264603 içinde OEIS ) .

Örnekler

Beşinci sıraya kadar her ana sınıftan bir Latin kare örneği veriyoruz.

${displaystyle {egin {bmatrix} 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 2 & 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 3 2 & 3 & 1 3 & 1 & 2end {bmatrix}}}$

${displaystyle {egin {bmatrix} 1 & 2 & 3 & 4 2 & 1 & 4 & 3 3 & 4 & 1 & 2 4 & 3 & 2 & 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 3 & 4 2 & 4 & 1 & 3 3 & 1 & 4 & 2 4 & 3 & 2 & 1end {bmatrix}}$

${displaystyle {egin {bmatrix} 1 & 2 & 3 & 4 & 5 2 & 3 & 5 & 1 & 4 3 & 5 & 4 & 2 & 1 4 & 1 & 2 & 5 & 3 5 & 4 & 1 & 3 & 2end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 1 & 4 & 5 2 & 4 & 1 & 5 & 2 & 1 & 4 & 1 & 5 & 3 3 & 4 & 1 & 5 & 3 & 3$

Sırasıyla aşağıdaki grupların çarpım tablolarını sunarlar:

• {0} - önemsiz 1 öğeli grup
• ${displaystyle mathbb {Z} _ {2}}$ - ikili grup
• ${displaystyle mathbb {Z} _ {3}}$ – döngüsel grup sipariş 3
• ${displaystyle mathbb {Z} _ {2} imes mathbb {Z} _ {2}}$ - Klein dört grup
• ${displaystyle mathbb {Z} _ {4}}$ - 4. dereceden döngüsel grup
• ${displaystyle mathbb {Z} _ {5}}$ - 5. dereceden döngüsel grup
• sonuncusu bir örnektir quasigroup veya daha doğrusu döngü ilişkisel olmayan.

Çaprazlar ve gökkuşağı eşleşmeleri

Bir enine Latin meydanında n her satırın bir hücre içerdiği hücreler, her sütun bir hücre içerir ve her sembolü içeren bir hücre vardır.

Bir Latin karesini tam olarak düşünebiliriz iki parçalı grafik burada satırlar bir parçanın köşeleri, sütunlar diğer parçanın köşeleri, her hücre bir kenardır (satırı ile sütunu arasında) ve semboller renklerdir. Latin karelerinin kuralları, bunun uygun bir kenar boyama. Bu tanımla, Latince enine, her kenarın farklı bir renge sahip olduğu bir eşleşmedir; böyle bir eşleştirmeye denir gökkuşağı eşleşmesi.

Bu nedenle, Latin kareler / dikdörtgenler ile ilgili birçok sonuç, başlıklarında "gökkuşağı eşleşmesi" terimi bulunan kağıtlarda bulunur ve bunun tersi de geçerlidir.^[7]

Bazı Latin karelerinde çaprazlama yoktur. Örneğin, ne zaman n eşittir n-tarafından-n Hücre değerinin bulunduğu Latin kare ben, j dır-dir (ben+j) mod n çapraz yoktur. İşte iki örnek:

${displaystyle {egin {bmatrix} 1 & 2 2 & 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 3 & 4 2 & 3 & 4 & 1 3 & 4 & 1 & 2 4 & 1 & 2 & 3end {bmatrix}}}$

1967'de, H. J. Ryser varsaydı ki, ne zaman n dır-dir garip, her n-tarafından-n Latin karesinde bir enine vardır.^[8]

1975'te S. K. Stein ve Brualdi, n dır-dir hatta, her n-tarafından-n Latin karesinde kısmi enine boyut n-1.^[9]

Stein'ın daha genel bir varsayımı, boyutun enine n-1 sadece Latin karelerinde değil, aynı zamanda herhangi bir n-tarafından-n dizisi n semboller, her sembol tam olarak göründüğü sürece n zamanlar.^[8]

Bu varsayımların bazı daha zayıf versiyonları kanıtlanmıştır:

• Her n-tarafından-n Latin karesi, 2 boyutunda kısmi enine kesite sahiptirn/3.^[10]
• Her n-tarafından-n Latin kare, kısmi bir enine boyuta sahiptir n - sqrt (n).^[11]
• Her n-tarafından-n Latin kare, kısmi bir enine boyuta sahiptir n - 11 günlük₂²(n).^[12]

Algoritmalar

Küçük kareler için permütasyonlar oluşturmak ve Latin kare özelliğinin karşılanıp karşılanmadığını test etmek mümkündür. Daha büyük kareler için, Jacobson ve Matthews'un algoritması, alan üzerinde düzgün bir dağılımdan örneklemeye izin verir. n × n Latin kareler.^[13]

Başvurular

İstatistik ve matematik

• İçinde deney tasarımı Latin kareler özel bir durumdur satır-sütun tasarımları iki kişilik engelleyici faktörler:^[14][15]

• İçinde cebir Latin kareler, grupları; özellikle Latin kareleri, çarpım tabloları (Cayley masaları ) nın-nin dörtlü gruplar. Değer tablosu bir Latin karesi oluşturan ikili bir işlemin, Latin kare özelliği.

Kodları düzeltme hatası

Latin karelerinin kümeleri dikey birbirlerine bir uygulama bulduk hata düzeltme kodları iletişimin basitten daha fazla gürültü türü tarafından rahatsız edildiği durumlarda beyaz gürültü örneğin, geniş bant İnternet'i elektrik hatları üzerinden iletmeye çalışırken.^[16][17][18]

İlk olarak, mesaj, sinyali herhangi bir belirli frekansta gürültüye karşı daha az savunmasız hale getiren yaygın bir yöntem olan çeşitli frekanslar veya kanallar kullanılarak gönderilir. Gönderilecek mesajdaki bir harf, ardışık zaman aralıklarında farklı frekanslarda bir dizi sinyal gönderilerek kodlanır. Aşağıdaki örnekte, A'dan L'ye kadar olan harfler, dört zaman diliminde dört farklı frekansta sinyaller gönderilerek kodlanmıştır. Örneğin C harfi, önce frekans 3, ardından 4, 1 ve 2 gönderilerek kodlanır.

${displaystyle {egin {matrix} A B C D end {matrix}} {egin {bmatrix} 1 & 2 & 3 & 4 2 & 1 & 4 & 3 3 & 4 & 1 & 2 4 & 3 & 2 & 1 end {bmatrix}} quad {egin {matrix} E F G H end {matrix}} {egin {bmatrix} 1 & 3 & 4 & 2 2 & 4 & 3 & 1 3 & 1 & 2 & 4 4 & 2 & 1 & 3 end {bmatrix}} quad {egin {matrix} I J K L end {matrix}} {egin {bmatrix} 1 & 4 & 2 & 3 2 & 3 & 1 & 4 3 & 2 & 4 & 1 4 & 1 & 3 & 2 end {bmatrix}}}$

On iki harfin kodlaması birbirine ortogonal olan üç Latin karesinden oluşur. Şimdi tüm iletim sırasında 1. ve 2. kanallarda ek gürültü olduğunu hayal edin. A harfi daha sonra şu şekilde alınacaktır:

${displaystyle {egin {matrix} 12 & 12 & 123 & 124 end {matrix}}}$

Diğer bir deyişle, birinci aralıkta hem frekans 1 hem de frekans 2'den sinyaller alıyoruz; üçüncü yuva 1, 2 ve 3 frekanslarından gelen sinyallere sahipken, gürültü nedeniyle, ilk iki yuvanın 1,1 mi 1,2 mi yoksa 2,1 mi yoksa 2,2 mi olduğunu artık bilemiyoruz. Ancak 1,2 durumu, yukarıdaki tablodaki bir harfle eşleşen bir dizi veren tek durumdur, A harfi. Benzer şekilde, üçüncü yuvadaki tüm frekanslarda bir statik patlaması hayal edebiliriz:

${displaystyle {egin {matrix} 1 & 2 & 1234 & 4 end {matrix}}}$

Yine, kodlamalar tablosundan iletilen A harfi olması gerektiği sonucunu çıkarabiliriz. Bu kodun tespit edebileceği hata sayısı, zaman aralığı sayısından bir azdır. Ayrıca, frekansların sayısının bir asal veya bir asalın gücü olması durumunda, ortogonal Latin karelerinin, olabildiğince verimli hata tespit kodları ürettiği de kanıtlanmıştır.

Matematiksel bulmacalar

Kısmen doldurulmuş bir karenin bir Latin kare oluşturmak için tamamlanıp tamamlanamayacağını belirleme sorunu NP tamamlandı.^[19]

Popüler Sudoku bulmacalar Latin karelerinin özel bir halidir; Sudoku bulmacasının herhangi bir çözümü Latin karesidir. Sudoku, dokuz belirli 3 × 3 bitişik alt karenin 1–9 rakamlarını da (standart sürümde) içermesi gerektiği gibi ek kısıtlama getirir. Ayrıca bakınız Sudoku Matematiği.

Daha yeni KenKen bulmacalar da Latin karelerine örnektir.

Masa oyunları

Latin kareleri, özellikle popüler soyut strateji oyunu olmak üzere birçok tahta oyununun temeli olarak kullanılmıştır. Kamisado.

Agronomik araştırma

Latin kareleri, deneysel hataları en aza indirmek için agronomik araştırma deneylerinin tasarımında kullanılır.^[20]

Hanedanlık armaları

Latin meydanı aynı zamanda şehrin kollarında yer almaktadır. Kanada İstatistik Kurumu,^[21] özellikle bahsediliyor blazon. Ayrıca, ürünün logosunda da görünür. Uluslararası Biyometrik Topluluğu.^[22]

Genellemeler

• Bir Latin dikdörtgen bir Latin karesinin genellemesidir, burada n sütunlar ve n olası değerler, ancak satır sayısı şundan daha küçük olabilir n. Her değer, her satırda ve sütunda en fazla bir kez görünmeye devam eder.
• Bir Graeco-Latin meydanı biri diğerinin üzerine yerleştirildiğinde her bir sıralı sembol çifti tam olarak bir kez görünecek şekilde iki Latin karesidir.
• Bir Latince hiperküp Latin karenin iki boyuttan birden çok boyuta genellemesidir.

Ayrıca bakınız

• Blok tasarımı
• Kombinatoryal tasarım
• Sekiz kraliçe yapboz
• Futoshiki
• Sihirli kare
• Latin karelerindeki problemler
• Rook'un grafiği Latin kareleri olan bir grafik renklendirmeler
• Sator Meydanı
• Vedik kare
• Kelime kare

Notlar

Referanslar

• Bailey, R.A. (2008). "6 Satır-Sütun tasarımları ve Latin kareleri hakkında 9 tane daha". Karşılaştırmalı Deneylerin Tasarımı. Cambridge University Press. ISBN  978-0-521-68357-9. BAY  2422352.
• Dénes, J .; Keedwell, A.D. (1974). Latin kareler ve uygulamaları. New York-Londra: Academic Press. s. 547. ISBN  0-12-209350-X. BAY  0351850.
• Shah, Kirti R .; Sinha, Bikas K. (1989). "4 Satır-Sütun Tasarımları". Optimal Tasarımlar Teorisi. İstatistik Ders Notları. 54. Springer-Verlag. s. 66–84. ISBN  0-387-96991-8. BAY  1016151.
• van Lint, J. H .; Wilson, R. M. (1992). Kombinatorik Kursu. Cambridge University Press. s.157. ISBN  0-521-42260-4.

daha fazla okuma

• Dénes, J. H .; Keedwell, A. D. (1991). Latin kareleri: Teori ve uygulamalardaki yeni gelişmeler. Ayrık Matematik Yıllıkları. 46. Paul Erdős (önsöz). Amsterdam: Academic Press. ISBN  0-444-88899-3. BAY  1096296.
• Hinkelmann, Klaus; Kempthorne, Oscar (2008). Deneylerin Tasarımı ve Analizi. I, II (İkinci baskı). Wiley. ISBN  978-0-470-38551-7. BAY  2363107.
  • Hinkelmann, Klaus; Kempthorne, Oscar (2008). Deney Tasarımı ve Analizi, Cilt I: Deneysel Tasarıma Giriş (İkinci baskı). Wiley. ISBN  978-0-471-72756-9. BAY  2363107.
  • Hinkelmann, Klaus; Kempthorne, Oscar (2005). Deney Tasarımı ve Analizi, Cilt 2: İleri Deneysel Tasarım (İlk baskı). Wiley. ISBN  978-0-471-55177-5. BAY  2129060.
• Knuth, Donald (2011). Bilgisayar Programlama Sanatı, Cilt 4A: Kombinatoryal Algoritmalar, Bölüm 1. Okuma, Massachusetts: Addison-Wesley. ISBN  978-0-201-03804-0.
• Laywine, Charles F .; Mullen, Gary L. (1998). Latin kareleri kullanan ayrık matematik. Ayrık Matematik ve Optimizasyonda Wiley-Interscience Serisi. New York: John Wiley & Sons, Inc. ISBN  0-471-24064-8. BAY  1644242.
• Shah, K. R .; Sinha, Bikas K. (1996). "Satır-sütun tasarımları". S. Ghosh ve C. R. Rao (ed.). Deney tasarımı ve analizi. Handbook of Statistics. 13. Amsterdam: North-Holland Publishing Co. s. 903–937. ISBN  0-444-82061-2. BAY  1492586.
• Raghavarao, Damaraju (1988). Deney Tasarımında Yapılar ve Kombinatoryal Problemler (1971 Wiley editörünün düzeltilmiş yeniden basımı). New York: Dover. ISBN  0-486-65685-3. BAY  1102899.
• Sokak, Anne Penfold; Sokak, Deborah J. (1987). Deneysel Tasarım Kombinatorikleri. New York: Oxford University Press. ISBN  0-19-853256-3. BAY  0908490.

Dış bağlantılar

• Weisstein, Eric W. "Latin Meydanı". MathWorld.
• Latin Kareler içinde Matematik Ansiklopedisi
• Latin Kareler içinde Çevrimiçi Tam Sayı Dizileri Ansiklopedisi