라틴 사각형

조합학 및 실험 설계에서 라틴 사각형은 n개의 다른 기호로 채워진 n × n 배열로, 각각은 각 행에 정확히 한 번, 각 열에 정확히 한 번 발생한다. 3×3 라틴 사각형의 예는 다음과 같다.

A	B	C
C	A	B
B	C	A

"라틴 사각형"이라는 이름은 라틴 문자를 기호로 사용한 레오나르드 오일러(1707–1783)의 수학 논문에서 영감을 받았으나,^[2] 어떤 기호도 사용할 수 있다: 위의 예에서 알파벳 순서 A, B, C는 정수 순서 1, 2, 3. 오일러는 라틴 사각형의 일반 이론을 시작했다.

역사

한국의 수학자 최석정은 1700년에 마법의 광장을 건설하기 위해 라틴어 순서 9의 정사각형 예시를 처음으로 출판하여 67년 리온하르트 오일러를 앞질렀다.^[3]

축소형식

라틴어 사각형은 첫 번째 행과 첫 번째 열이 모두 자연적인 순서로 되어 있으면 축소(정상화 또는 표준화된 형태)된다고 한다.^[4] 예를 들어 위의 라틴 사각형은 첫 번째 열이 A, B, C가 아니라 A, C, B이기 때문에 줄어들지 않는다.

모든 라틴어 사각형은 행과 열을 재순열하여 줄일 수 있다. 여기서 위의 행렬의 두 번째와 세 번째 행을 전환하면 다음과 같은 제곱이 나온다.

A	B	C
B	C	A
C	A	B

이 라틴어 정사각형은 축소되었다; 첫 번째 행과 첫 번째 열은 모두 알파벳순으로 배열되어 있다.

특성.

직교 배열 표현

n ×n 라틴 사각형의 각 항목이 3중(r,c,s)으로 쓰여진다면, 여기서 r은 행이고 c는 컬럼이고 s는 기호라면, 우리는 사각형의 직교 배열 표현이라 불리는 n개의² 3중 배열을 얻는다. 예를 들어, 라틴 사각형의 직교 배열 표현

1	2	3
2	3	1
3	1	2

이다

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

여기서, 3행(2, 3, 1)은 2행과 3열에 기호 1이 있음을 의미한다. 직교 배열은 대개 다음과 같이 3배수가 행인 배열 형태로 작성된다.

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

라틴 사각형의 정의는 직교 배열의 측면에서 다음과 같이 쓸 수 있다.

• 라틴어 사각형은² n 3중(r, c, s)의 집합으로, 여기서 1≤ r, c, s ≤ n은 순서 쌍(r, c)이 모두 구별되고, 순서 쌍(r, s)은 모두 구별되며, 순서 쌍(c, s)은 모두 구별된다.

즉, n개의² 순서 쌍(r, c)이 모두 1 i i, j ≤ n을 각각 한 번씩 갖는 쌍(i, j)임을 의미한다. 순서쌍(r, s)과 순서쌍(c, s)도 마찬가지다.

직교 배열 표현은 행, 열 및 기호가 아래에 분명히 나타나듯이 다소 유사한 역할을 한다는 것을 보여준다.

라틴 제곱의 동등성 등급

라틴어 광장의 많은 작업들은 다른 라틴어 광장을 생산한다(예를 들어, 그것을 뒤집는다).

행을 퍼트리고 기둥을 퍼트리고, 라틴 사각형의 기호 이름을 퍼트리면, 우리는 첫 번째와 동위원소라고 하는 새로운 라틴 사각형을 얻게 된다. 동위원소법은 등가관계이므로 모든 라틴 제곱의 집합은 동위원소 등급이라고 하는 하위 집합으로 나뉘는데, 같은 등급의 두 칸은 동위원소, 다른 등급의 두 칸은 동위원소가 아니다.

또 다른 유형의 연산은 라틴 사각형의 직교 배열 표현을 사용하여 설명하기가 가장 쉽다. 만일 우리가 각 3중으로 된 3개의 항목(즉, 배열 형태에 있는 3개의 기둥을 허용)을 체계적이고 일관성 있게 재정렬하면, 또 다른 직교 배열(따라서, 또 다른 라틴 사각형)을 얻는다. 예를 들어 각 삼중(r,c,s)을 제곱을 전치하는 것에 해당하는 (c,r,s)로 교체하거나, 각 삼중(r,c,s)을 (c,s,r)로 교체할 수 있는데, 이것은 더 복잡한 작업이다. 다 합쳐서 "아무 것도 하지 말라"를 포함한 6개의 가능성이 있는데, 이것은 우리에게 원래의 사각형의 결합체라고 불리는 6개의 라틴 사각형을 준다.^[5]

마지막으로, 우리는 이 두 개의 동등성 연산을 결합할 수 있다: 두 개의 라틴 제곱은 파라토픽이며, 또한 하나의 라틴 제곱이 다른 제곱의 결합에 동위원소인 경우 주 등급 동위원소라고 한다. 이것은 다시 주종류, 종류 또는 파라토피류라고 불리는 등가물류와의 동등성 관계다.^[5] 각 메인 클래스는 최대 6개의 동위원소 클래스를 포함한다.

숫자

기호 1,2,...,n이 있는 n × n 라틴 제곱의 숫자 L에_n 대해 쉽게 계산 가능한 공식은 알려져 있지 않다. 큰 n에 대해 알려진 가장 정확한 상한과 하한은 멀리 떨어져 있다. 한 가지 고전적인 결과는^[6] 다음과 같다.

라틴어 정사각형의 수에 대한 간단하고 명시적인 공식은 1992년에 발표되었지만, 항 수의 기하급수적인 증가로 인해 여전히 쉽게 계산할 수 없다. n × n 라틴 제곱의 숫자 L에_n 대한 이 공식은

여기서 B는_n 모든 n × n {0, 1} 행렬의 집합이고, σ₀(A)는 매트릭스 A의 0 항목 수, per(A)는 매트릭스 A의 상설이다.^[7]

아래 표에는 알려진 모든 정확한 값이 포함되어 있다. 그 수가 엄청나게 빠르게 증가하고 있음을 알 수 있다. 각 n에 대해 라틴 사각형 수를 합한 수(OEIS에서 순서 A002860)는 감소된 라틴 사각형 수(OEIS에서 순서 A000315)의 n!(n - 1)배이다.

다양한 크기의 라틴 사각형 수

n	크기가 n인 축소된 라틴어 제곱 (OEIS에서 시퀀스 A000315)	크기가 n인 모든 라틴어 정사각형 (OEIS에서 시퀀스 A002860)
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161,280
6	9,408	812,851,200
7	16,942,080	61,479,419,904,000
8	535,281,401,856	108,776,032,459,082,956,800
9	377,597,570,964,258,816	5,524,751,496,156,892,842,531,225,600
10	7,580,721,483,160,132,811,489,280	9,982,437,658,213,039,871,725,064,756,920,320,000
11	5,363,937,773,277,371,298,119,673,540,771,840	776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
12	1.62 × 1044
13	2.51 × 1056
14	2.33 × 1070
15	1.50 × 1086

각 n에 대해 각 동위원소 등급(OEIS의 경우 시퀀스 A040082)은 최대 (n!)³ 라틴 사각형(정확한 숫자는 다름)을 포함하고, 각 메인 클래스(OEIS의 시퀀스 A003090)는 1, 2, 3 또는 6개의 동위원소 클래스를 포함한다.

라틴 제곱의 동등성 등급

n	주요 계급 (OEIS에서 시퀀스 A003090)	동위원소 분류 (OEIS에서 시퀀스 A040082)	구조적으로 뚜렷한 사각형 (OEIS에서 시퀀스 A264603)
1	1	1	1
2	1	1	1
3	1	1	1
4	2	2	12
5	2	2	192
6	12	22	145,164
7	147	564	1,524,901,344
8	283,657	1,676,267
9	19,270,853,541	115,618,721,533
10	34,817,397,894,749,939	208,904,371,354,363,006
11	2,036,029,552,582,883,134,196,099	12,216,177,315,369,229,261,482,540

n = 1 ~ 7에 대한 구조적으로 구별되는 라틴어 사각형(즉, 기호의 회전, 반사 및/또는 순열로 제곱을 동일하게 만들 수 없음)의 수는 각각 1, 1, 1, 12, 192, 145164, 1524901344(OEIS에서 연속 A264603)이다.

예

우리는 각각의 메인 클래스에서 5번까지 라틴어 사각형의 한 예를 든다.

${\displaystyle {\bmatrix}1\end{bmatrix}\nd{bmatrix}\nd{bmatrix}\nd{bmatrix}\nd{bmatrix}}\nd{bmatrix}\nd{bmatrix}1&3\n3\nd{bmatrix}}}}}}}}nd}}}nd}}}$ ${\displaystyle {\begin{bmatrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4\\2&4&1&3\\3&1&4&2\\4&3&2&1\end{bmatrix}}}$ ${\displaystyle {\begin{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&2\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4&5\\2&4&1&5&3\\3&5&4&2&1\\4&1&5&3&2\\5&3&2&1&4\end{bmatrix}}}$

이들은 각각 다음과 같은 그룹의 곱셈표를 제시한다.

• {0} – 사소한 1개 항목 그룹
• ${\displaystyle {\mathbb{Z}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$}} $$– 이진 그룹
• ${\displaystyle {\mathbb{Z}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ $$– 순서 3의 순환 그룹
• ${\displaystyle {\mathbb{Z}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ $$– 클라인 4-그룹
• ${\displaystyle {\mathbb{Z}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ $$– 순서 4의 순환 그룹
• ${\displaystyle {\mathbb{Z}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ $$– 순서 5의 순환 그룹
• 마지막은 퀘이시그룹, 즉 연관성이 없는 루프의 예다.

횡단면 및 무지개 일치

라틴 사각형의 횡단면이란 n개의 셀을 선택하는 것으로, 각 행은 하나의 셀을 포함하고, 각 열은 하나의 셀을 포함하고, 각 기호를 포함하는 하나의 셀이 있다.

행이 한 부분의 꼭지점이고, 열은 다른 부분의 꼭지점이며, 각 셀은 가장자리(행과 열 사이), 기호는 색상인 완전한 양분 그래프로 간주할 수 있다. 라틴어 사각형의 규칙은 이것이 적절한 가장자리 색소임을 암시한다. 이 정의와 함께, 라틴어 횡단선은 각각의 가장자리의 색이 다른 매칭이다; 그러한 매칭은 무지개 매칭이라고 불린다.

따라서 라틴어 정사각형/직사각형에 대한 많은 결과가 제목에 "레인보우 매칭"이라는 용어가 붙은 논문에 수록되어 있으며, 그 반대의 경우도 마찬가지다.^[8]

어떤 라틴어 사각형들은 횡단적인 것이 없다. 예를 들어, n이 짝수일 때, cell i,j의 값이 (i+j) mod n인 n-by-n 라틴 사각형은 횡단적인 것이 없다. 여기 두 가지 예가 있다.

1967년, H. J. 라이저는 n이 이상할 때, 모든 n-by-n 라틴 광장은 횡단성을 가지고 있다고 추측했다.^[9]

1975년, S. K. 스타인과 브루알디는 n이 짝수일 때, 모든 n-by-n 라틴 광장은 n-1 크기의 부분 횡단체를 가지고 있다고 추측했다.^[10]

스타인에 대한 보다 일반적인 추측은 각 기호가 정확히 n번 나타나는 한, 크기가 n-1인 횡단적인 크기가 라틴 사각형뿐만 아니라 n by n 기호의 배열에도 존재한다는 것이다.^[9]

이러한 추측의 일부 약한 버전이 증명되었다.

• 모든 n-by-n 라틴 사각형에는 2n/3 크기의 부분 횡단면이 있다.^[11]
• 모든 n-by-n 라틴 사각형에는 n - sqrt(n) 크기의 부분 횡단면이 있다.^[12]
• 모든 n-by-n 라틴 사각형에는 n - 11 log²
  ₂(n) 크기의 부분 횡단면이 있다.^[13]

알고리즘

작은 사각형의 경우 순열을 생성하고 라틴 사각형 특성이 충족되는지 여부를 테스트할 수 있다. 더 큰 사각형의 경우, Jacobson과 Matthews의 알고리즘은 n × n 라틴 사각형의 공간에 걸친 균일한 분포로부터 표본을 추출할 수 있다.^[14]

적용들

통계와 수학

• 실험 설계에서 라틴 제곱은 두 블럭화 요인에 대한 행-기둥 설계의 특별한 경우다.^[15][16]
• 대수학에서 라틴 사각형은 그룹의 일반화와 관련이 있다. 특히 라틴 사각형은 퀘이그룹의 곱셈표(Cayley tables)로 특징지어진다. 값표가 라틴 사각형을 이루는 이진 연산(binary operation)은 라틴 사각형 속성을 따른다고 한다.

코드 수정 오류

서로 직교하는 라틴어 사각형 집합은 전원선을 통해 광대역 인터넷을 전송하려고 시도할 때와 같이 단순한 백색 소음보다 더 많은 유형의 소음에 의해 통신이 교란되는 상황에서 코드를 오류 수정하는 어플리케이션을 발견했다.^[17][18][19]

첫째로, 메시지는 어떤 특정 주파수에서 신호의 노이즈에 덜 취약하게 만드는 일반적인 방법인 여러 주파수 또는 채널을 사용하여 전송된다. 송신할 메시지의 문자는 연속적인 시간 간격으로 서로 다른 주파수에서 일련의 신호를 보내 인코딩된다. 아래 예에서 A에서 L까지의 문자는 4개의 다른 주파수에서 4개의 시간 슬롯으로 신호를 보내 인코딩된다. 예를 들어, 문자 C는 먼저 주파수 3으로, 그 다음 4, 1, 2로 전송함으로써 암호화된다.

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

12자의 인코딩은 서로 직교하는 세 개의 라틴 사각형으로부터 형성된다. 이제 전체 전송 중에 채널 1과 2에 노이즈가 추가된다고 상상해 보십시오. 그러면 A라는 글자는 다음과 같이 주워들곤 했다.

즉, 첫 번째 슬롯에서는 주파수 1과 주파수 2의 신호를 모두 수신하는 반면, 세 번째 슬롯은 주파수 1, 2, 3의 신호를 수신한다. 소음 때문에 처음 두 슬롯이 1,1인지 1,2인지, 2,1인지 2,2인지 더 이상 구분할 수 없다. 그러나 위의 표에 있는 글자 A와 일치하는 시퀀스를 산출하는 것은 1,2 케이스밖에 없다. 마찬가지로, 우리는 세 번째 슬롯의 모든 주파수에서 정전기 폭발을 상상할 수 있다.

다시 한번 인코딩 테이블에서 그것이 A가 전송되고 있는 문자임에 틀림없다는 것을 유추할 수 있다. 이 코드가 나타낼 수 있는 오류 수는 시간 간격 수보다 한 개 적다. 또한 주파수 수가 프라임 또는 프라임의 힘일 경우 직교 라틴 사각형은 가능한 한 효율적인 오류 감지 코드를 생성한다는 것이 입증되었다.

수학 퍼즐

부분적으로 채워진 사각형이 라틴어 사각형을 형성할 수 있는지 여부를 결정하는 문제는 NP-완전이다.^[20]

인기 있는 스도쿠 퍼즐은 라틴어 사각형의 특별한 경우다; 스도쿠 퍼즐에 대한 해결책은 라틴어 사각형이다. 스도쿠는 9개의 특정 3×3 인접 서브스퀘어에도 1–9(표준 버전)의 숫자가 포함되어야 한다는 추가 제한을 부과한다. 스도쿠의 수학도 참조하십시오.

더 최근의 켄켄 퍼즐도 라틴어 사각형의 예들이다.

보드 게임

라틴 스퀘어는 여러 보드 게임, 특히 인기 추상 전략 게임 카미사도의 기본으로 이용되어 왔다.

아그로믹스

라틴 사각형은 실험 오류를 최소화하기 위해 농학 연구 실험의 설계에 사용된다.^[21]

헤럴드리

라틴어 광장은 또한 캐나다 통계학회의 팔에 나타나 있으며,^[22] 그 블레이저에서 구체적으로 언급되고 있다. 또한 국제생체인식학회 로고에도 등장한다.^[23]

일반화

• 라틴 직사각형은 열과 가능한 값이 n개인 라틴 사각형을 일반화한 것이지만 행 수는 n보다 작을 수 있다. 각 값은 여전히 각 행과 열에 한 번 나타난다.
• 그래코-라틴 정사각형은 한 쌍이 다른 한 쌍 위에 놓일 때 각각 순서가 정해진 한 쌍의 기호가 정확히 한 번 나타나는 두 개의 라틴어 정사각형이다.
• 라틴어 하이퍼큐브는 라틴어 사각형을 2차원에서 다차원으로 일반화한 것이다.

참고 항목

• 블록 설계
• 조합 설계
• 퀸스 퍼즐 8개
• 후토시키
• 매직 스퀘어
• 라틴어 사각형의 문제
• Rook의 그래프, 라틴 사각형을 색상으로 표시한 그래프
• 사토르 광장
• 베딕 광장
• 워드 스퀘어

메모들

참조

• 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. p. 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. Vol. 54. Springer-Verlag. pp. 66–84. ISBN 0-387-96991-8. MR 1016151. {{cite book}}: 외부 링크 위치 series= (도움말)
• van Lint, J. H.; Wilson, R. M. (1992). A Course in Combinatorics. Cambridge University Press. p. 157. ISBN 0-521-42260-4.

추가 읽기

• Dénes, J. H.; Keedwell, A. D. (1991). Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics. Vol. 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. Vol. I, II (Second ed.). 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 (Second ed.). Wiley. ISBN 978-0-471-72756-9. MR 2363107.
  • Hinkelmann, Klaus; Kempthorne, Oscar (2005). Design and Analysis of Experiments, Volume 2: Advanced Experimental Design (First ed.). 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". In S. Ghosh and C. R. Rao (ed.). Design and analysis of experiments. Handbook of Statistics. Vol. 13. Amsterdam: North-Holland Publishing Co. pp. 903–937. ISBN 0-444-82061-2. MR 1492586.
• Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). 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 (2nd edition (November 28, 2017) ed.). Springer. pp. 267–282.

외부 링크

• Weisstein, Eric W. "Latin Square". MathWorld.
• 수학 백과사전 속의 라틴 광장
• 온라인 정수 시퀀스 백과사전의 라틴 제곱