직교 배열

틀:위키데이터 속성 추적 조합론에서 직교 배열(直交配列, 틀:Llang)은 좌표들의 부분 집합으로 제한하였을 때 모든 가능한 벡터들이 균등하게 분포되어 있는, 주어진 유한 집합 위의 벡터들의 유한 집합이다.

정의

자연수 $t\in \mathbb{N}$가 주어졌다고 하자.

$t$-직교 배열 $(\mathrm{\Sigma },B)$은 다음과 같은 데이터로 주어진다.

• 크기 $q$의 유한 집합 $\mathrm{\Sigma }$. 이를 알파벳이라고 하며, 그 원소를 수준(水準, 틀:Llang)이라고 한다.
• 자연수 $n\in \mathbb{N}$. 이를 인자수(因子數, 틀:Llang)라고 한다.
• 부분 집합 $B\subseteq {\mathrm{\Sigma }}^n$. 그 원소를 실험 실행(實驗實行, 틀:Llang)라고 한다.

이는 다음 조건을 만족시켜야 한다.

• ${\mathrm{\Sigma }}^n$의 $n$개의 좌표 가운데 임의의 $t$개를 골랐을 때, 수준의 모든 $t$-순서쌍들은 (선택한 레벨 및 좌표에 상관없이) 같은 수 ${\lambda }_t$번 만큼 등장한다. 즉, 임의의 단사 함수 $f:\{1,2,\dots ,t\}\to \{1,\dots ,n\}$ 및 임의의 $x\in {\mathrm{\Sigma }}^t$에 대하여, 자연수 ${\lambda }_t=|\{b\in B:\mathrm{\forall }1\le i\le t:x_i=b_{f(i)}\}|\in \mathbb{N}$는 $f$ 및 $x$의 선택에 의존하지 않는다.

이는 해밍 결합 도식 $\mathrm{H}(n,\mathrm{\Sigma })$ 속의 블록 설계의 개념과 같다.

여기서, $t$를 직교 배열의 강도(強度, 틀:Llang)라고 하며, ${\lambda }_t$를 $t$-직교 배열의 지수(指數, 틀:Llang)라고 한다.

성질

상수 ${\lambda }_t$에 대한 $t$-직교 배열 $(\mathrm{\Sigma },B\subseteq {\mathrm{\Sigma }}^n)$가 주어졌다고 하자. 그렇다면,

• 임의의 자연수 $t^{\prime }\le t$
• 임의의 단사 함수 $f:\{1,2,\dots ,t^{\prime }\}\to \{1,2,\dots ,n\}$
• 임의의 $x\in {\mathrm{\Sigma }}^{t^{\prime }}$

에 대하여, 다음이 성립한다.

$|\{b\in B:\mathrm{\forall }1\le i\le t^{\prime }:x_i=b_{f(i)}\}|={\lambda }_{t^{\prime }}={\lambda }_t|\mathrm{\Sigma }{|}^{t-t^{\prime }}$

즉,

${\lambda }_0={\lambda }_t|\mathrm{\Sigma }{|}^t$

를 정의하면, 임의의 $t$-직교 배열은 임의의 $t^{\prime }\le t$에 대하여 $t^{\prime }$-직교 배열을 이루며, 그 상수는 ${\lambda }_{t^{\prime }}={\lambda }_0|\mathrm{\Sigma }{|}^{-t^{\prime }}$이다. 여기서, ${\lambda }_0$는 물론 $B$의 크기와 같다.

이에 따라, 임의의 ${\mathrm{\Sigma }}^n$ 속에서 다음과 같은 포함 관계가 성립한다.

$\mathrm{Pow}({\mathrm{\Sigma }}^n)$ = 0-직교 배열 ⊇ 1-직교 배열 ⊇ 2-직교 배열 ⊇ … ⊇ $n$-직교 배열 = $\{\varnothing ,{\mathrm{\Sigma }}^n\}$

예

자명한 직교 배열

임의의 유한 집합 $\mathrm{\Sigma }$에 대하여, ${\mathrm{\Sigma }}^n$ 속의 유일한 $n$-직교 배열은 $B=\varnothing$ 및 $B={\mathrm{\Sigma }}^n$이며, 이 경우 각각 ${\lambda }_n=0$ 및 ${\lambda }_n=1$이다.

반대로, ${\mathrm{\Sigma }}^n$의 임의의 부분 집합은 0-직교 배열을 이룬다.

라틴 방진

틀:본문 $q\times q$ 라틴 방진 $M$은

$({\lambda }_2,{\lambda }_1,{\lambda }_0)=(1,q,q^2)$

인 2-직교 배열

$\mathrm{\Sigma }=\{1,2,\dots ,q\}$

$B\subseteq {\mathrm{\Sigma }}^3$

$|B|={\lambda }_0=q^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-직교 배열의 예

알파벳

$\mathrm{\Sigma }=\{𝖠,𝖡,𝖢,𝖣\}$

위에서, 다음 표의 16개 행들로 구성된 부분 집합

$B⊊{\mathrm{\Sigma }}^5$

$|B|={\lambda }_0=16$

은 지수

$({\lambda }_2,{\lambda }_1,{\lambda }_0)=(1,4,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

알파벳

$\mathrm{\Sigma }=\{𝖠,𝖡,𝖢\}$

위에서, 다음 표의 27개 행들로 구성된 부분 집합

$B⊊{\mathrm{\Sigma }}^5$

$|B|={\lambda }_0=27$

은 지수

$({\lambda }_2,{\lambda }_1,{\lambda }_0)=(3,9,27)$

을 갖는 2-직교 배열을 이룬다.

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년에 칼리암푸디 라다크리슈나 라오가 도입하였다.

외부 링크

• 틀:Eom
• 틀:매스월드