직교 배열
조합론에서 직교 배열(直交配列, 영어: orthogonal array)은 좌표들의 부분 집합으로 제한하였을 때 모든 가능한 벡터들이 균등하게 분포되어 있는, 주어진 유한 집합 위의 벡터들의 유한 집합이다.[1]
정의
편집자연수 가 주어졌다고 하자.
-직교 배열 은 다음과 같은 데이터로 주어진다.
- 크기 의 유한 집합 . 이를 알파벳이라고 하며, 그 원소를 수준(水準, 영어: level)이라고 한다.
- 자연수 . 이를 인자수(因子數, 영어: number of factors)라고 한다.
- 부분 집합 . 그 원소를 실험 실행(實驗實行, 영어: experimental run)라고 한다.
이는 다음 조건을 만족시켜야 한다.
- 의 개의 좌표 가운데 임의의 개를 골랐을 때, 수준의 모든 -순서쌍들은 (선택한 레벨 및 좌표에 상관없이) 같은 수 번 만큼 등장한다. 즉, 임의의 단사 함수 및 임의의 에 대하여, 자연수 는 및 의 선택에 의존하지 않는다.
이는 해밍 결합 도식 속의 블록 설계의 개념과 같다.[2]
여기서, 를 직교 배열의 강도(強度, 영어: strength)라고 하며, 를 -직교 배열의 지수(指數, 영어: index)라고 한다.
성질
편집상수 에 대한 -직교 배열 가 주어졌다고 하자. 그렇다면,
- 임의의 자연수
- 임의의 단사 함수
- 임의의
에 대하여, 다음이 성립한다.
즉,
를 정의하면, 임의의 -직교 배열은 임의의 에 대하여 -직교 배열을 이루며, 그 상수는 이다. 여기서, 는 물론 의 크기와 같다.
이에 따라, 임의의 속에서 다음과 같은 포함 관계가 성립한다.
- = 0-직교 배열 ⊇ 1-직교 배열 ⊇ 2-직교 배열 ⊇ … ⊇ -직교 배열 =
예
편집자명한 직교 배열
편집임의의 유한 집합 에 대하여, 속의 유일한 -직교 배열은 및 이며, 이 경우 각각 및 이다.
반대로, 의 임의의 부분 집합은 0-직교 배열을 이룬다.
라틴 방진
편집라틴 방진 은
인 2-직교 배열
에 해당한다.
(즉, 2-직교 배열과 라틴 방진 사이의 관계는 2-블록 설계와 2-슈타이너 계 사이의 관계와 같다.)
예를 들어, 3×3 라틴 방진
1 2 3 2 3 1 3 1 2
은 다음과 같은 표의 9개 행들로 구성되는 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
2-직교 배열의 예
편집알파벳
위에서, 다음 표의 16개 행들로 구성된 부분 집합
은 지수
을 갖는 2-직교 배열을 이룬다.
A A A A A A B B B B A C C C C A D D D D B A D B C B B C A D B C B D A B D A C B C A B C D C B A D C C C D A B C D C B A D A C D B D B D C A D C A B D D D B A C
알파벳
위에서, 다음 표의 27개 행들로 구성된 부분 집합
은 지수
을 갖는 2-직교 배열을 이룬다.[3]
A A A A A A A B A B A A C A C A B A B B A B B B C A B C B A A C A C C A C B C A A C C C B B A A C A B A B C B B A C C C B B A A B B B B A C B B C A A B C A B C B C B B A B C C B B C A A B A C A B B B C A C B C C B A C B C B B C C C B C C A C C A A C C C B A A C C C A B
역사
편집1947년에 칼리암푸디 라다크리슈나 라오가 도입하였다.[4]
각주
편집- ↑ Hedayat, Abdos Samad; Sloane, Neil James Alexander; Stufken, John (1999). 《Orthogonal arrays: theory and applications》. Springer Series in Statistics (영어). Springer-Verlag. doi:10.1007/978-1-4612-1478-6. ISBN 978-0-387-98766-8. ISSN 0172-7397. Zbl 0935.05001.
- ↑ Delsarte, Philippe; Levenshtein, Vladimir Iosifovich (1998년 10월). “Association schemes and coding theory”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 44 (6): 2477–2504. doi:10.1109/18.720545. ISSN 0018-9448.
- ↑ Keedwell, A. Donald; Denes, József (2015). 《Latin squares and applications》 (영어) 2판. North-Holland. doi:10.1016/B978-0-444-63555-6.50016-7. Zbl 1318.05001.
- ↑ Rao, Calyampudi Radhakrishna (1947). “Factorial experiments derivable from combinatorial arrangements of arrays”. 《Supplement to the Journal of the Royal Statistical Society》 (영어) 9 (1): 128–139. doi:10.2307/2983576. JSTOR 2983576.
외부 링크
편집- “Orthogonal array”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Orthogonal array”. 《Wolfram MathWorld》 (영어). Wolfram Research.