라틴 직사각형

결합수학에서 라틴 직사각형은 r × n 행렬(여기서 r r n)이며, 일반적으로 n 기호를 사용하여 숫자 1, 2, 3, ..., n 또는 0, 1, ..., n - 1을 항목으로 사용하며, 어떤 행이나 열에 한 번 이상 숫자가 발생하지 않는다.^[1]

n × n 라틴 사각형은 라틴 사각형이라고 불린다.

3 × 5 라틴 직사각형의 예는 다음과 같다.^[2]

0	1	2	3	4
3	4	0	1	2
4	0	3	2	1

정규화

라틴어 직사각형은 첫 번째 행이 자연 순서이고 첫 번째 열도 자연 순서일 경우 정규화(또는 축소)라고 불린다.^[3][4]

위의 예는 정규화되지 않았다.

열거

L(k, n)은 정규화된 k × n 라틴 직사각형의 수를 나타낸다.그러면^[5] 총 k × n 라틴 직사각형 수는

$(n-1)!L(k,n)}{(n-k)!}}.}$

2 × n 라틴 직사각형은 고정된 점이 없는 순열에 해당한다.이런 순열은 불협화음 순열이라고 불려왔다.^[3]주어진 순열과 불일치하는 순열의 열거는 유명한 problem des rencontents이다.두 순열과 불일치하는 순열의 열거는 다른 순열의 단순한 주기적 변화로 알려져 있다.^[3]

작은 크기의 정규화된 라틴 직사각형 수 L(k, n)은 다음과^[5] 같이 주어진다.

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

k = 1일 때, 즉, 행이 하나뿐인데, 라틴 직사각형이 정상화되기 때문에 이 행이 될 수 있는 것을 선택할 수 없다.표에는 또한 L(n - 1, n) = L(n, n)이 표시되는데, 이는 행이 하나만 누락된 경우 각 열의 누락된 항목은 라틴 사각형 속성에서 결정할 수 있고 직사각형은 라틴 사각형으로 고유하게 확장될 수 있기 때문이다.

확장성

한 행이 빠진 라틴어 직사각형을 위에서 언급한 라틴어 사각형까지 확장할 수 있는 특성은 크게 강화될 수 있다.즉, r < n이라면, 홀의 결혼 정리를 이용하여 n - r × n 라틴 사각형에 n - r 행을 추가하여 라틴 광장을 형성하는 것이 가능하다.^[6]

반라틴 정사각형

반라틴 정사각형은 또 다른 형태의 불완전한 라틴어 정사각형이다.반라틴 정사각형은 n × n 배열 L로, 어떤 위치는 비어 있고 다른 위치는 정수 {0, 1, ..., n - 1} 중 하나에 의해 점유된다. 따라서 L에서 정수 k가 발생하면 n번 발생하고 동일한 행이나 열에 2k가 속하지 않는다.만약 m이 L에서 다른 정수가 발생한다면, L은 지수 m을 가진다.^[7]

예를 들어, 순서 5와 색인 3의 반라틴 제곱은 다음과 같다.^[7]

1		0		2
	2	1		0
0	1		2
2	0		1
		2	0	1

순서 n과 지수 m의 반라틴 사각형은 nm를 채운 위치를 갖는다.반라틴 광장이 라틴 광장으로 완성될 수 있을까 하는 의문이 생긴다.다소 놀랍게도 대답은 항상이다.

L을 순서 n과 지수 m의 반-라틴 제곱으로 하고 여기서 m < n을 사용하라.그러면 L은 라틴어 광장으로 완성될 수 있다.^[7]

이를 증명하는 한 가지 방법은 순서 n과 지수 m의 반-라틴 사각형이 m × n 라틴 직사각형과 동일하다는 것을 관찰하는 것이다.Let L = a는_ij 라틴 직사각형이 되고 S = b는_ij 반라틴 정사각형이 되도록 하면 동등성은 다음과 같이 주어진다^[8].

${\displaystyle b_{ij}=k{\text{{}만약에 또는 }{kj}=i.}$

예를 들어, 3×5 라틴 직사각형

0	1	2	3	4
3	4	1	0	2
1	0	4	2	3

순서 5와 지수 3의 반라틴 제곱과 동일하다.^[8]

0	2		1
2	0	1
		0	2	1
1			0	2
	1	2		0

예를 들어, 라틴 직사각형에서는 a₁₀ = 3이므로, 반라틴 사각형에서는 b = 1이다₃₀.

적용들

통계에서 라틴 직사각형은 실험 설계에 응용이 있다.

참고 항목

• 조합 설계
• 레인보우 매칭

메모들

참조

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), 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, A. D. (1974), Latin squares and their applications, New York-London: Academic Press, p. 547, ISBN 0-12-209350-X, MR 0351850

추가 읽기

• Mirsky, L. (1971), Transversal theory : an account of some aspects of combinatorial mathematics, Academic Press, ISBN 0-12-498550-5, OCLC 816921720
• Riordan, John (2002) [1958], Introduction to Combinatorial Analysis, Dover, ISBN 978-0-486-42536-8

외부 링크

• Weisstein, Eric W., "Latin Rectangle", mathworld.wolfram.com, retrieved 2020-07-12