조합론 에서 존슨 결합 도식 (Johnson結合圖式, 영어 : Johnson scheme )은 주어진 해밍 무게 의 벡터들로 구성된, 2진 해밍 결합 도식 의 부분 결합 도식이다.
다음이 주어졌다고 하자.
크기
n
{\displaystyle n}
유한 집합
S
{\displaystyle S}
자연수
k
≤
n
{\displaystyle k\leq n}
그렇다면, 다음을 정의하자.
X
=
Pow
k
(
S
)
{\displaystyle X=\operatorname {Pow} _{k}(S)}
S
{\displaystyle S}
k
{\displaystyle k}
부분 집합 들의 집합족 이다.각
i
∈
{
0
,
1
…
,
n
}
{\displaystyle i\in \{0,1\dotsc ,n\}}
u
,
v
∈
X
{\displaystyle u,v\in X}
이항 관계
u
∼
i
v
⟺
d
H
(
u
,
v
)
=
2
i
{\displaystyle u\sim _{i}v\iff \operatorname {d_{H}} (u,v)=2i}
d
H
{\displaystyle \operatorname {d_{H}} }
해밍 거리 ) 그렇다면,
(
X
,
n
,
(
∼
i
)
0
≤
i
≤
n
)
{\displaystyle (X,n,(\sim _{i})_{0\leq i\leq n})}
결합 도식 을 이루며, 이를
(
k
,
n
)
{\displaystyle (k,n)}
영어 : binary Johnson association scheme )
J
2
(
k
,
n
)
{\displaystyle \operatorname {J} _{2}(k,n)}
q
{\displaystyle q}
q
≥
3
{\displaystyle q\geq 3}
편집
다음이 주어졌다고 하자.
유한 점을 가진 집합
(
Σ
,
∙
)
{\displaystyle (\Sigma ,\bullet )}
|
Σ
|
≥
2
{\displaystyle |\Sigma |\geq 2}
∙
{\displaystyle \bullet }
해밍 무게 를 정의할 수 있다.두 양의 정수
0
<
k
≤
n
{\displaystyle 0<k\leq n}
그렇다면, 다음과 같은 두 함수를 정의할 수 있다.
e
,
f
:
Σ
n
×
Σ
n
→
{
0
,
1
,
…
,
n
}
{\displaystyle e,f\colon \Sigma ^{n}\times \Sigma ^{n}\to \{0,1,\dotsc ,n\}}
e
:
(
u
,
v
)
↦
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
u
i
=
v
i
≠
∙
}
|
{\displaystyle e\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}=v_{i}\neq \bullet \}\right|}
f
:
(
u
,
v
)
↦
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
u
i
≠
∙
≠
v
i
}
|
{\displaystyle f\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}\right|}
(만약
|
Σ
|
≤
2
{\displaystyle |\Sigma |\leq 2}
e
=
f
{\displaystyle e=f}
이제,
∙
{\displaystyle \bullet }
해밍 무게 가
k
{\displaystyle k}
n
{\displaystyle n}
Σ
{\displaystyle \Sigma }
W
k
(
Σ
n
)
⊆
Σ
n
=
{
u
∈
Σ
n
:
k
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
u
i
≠
∙
}
|
}
{\displaystyle \operatorname {W} _{k}(\Sigma ^{n})\subseteq \Sigma ^{n}=\left\{u\in \Sigma ^{n}\colon k=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \}|\right\}}
을 생각하자. 이 위에, 이항 관계
u
∼
i
,
j
v
⟺
(
e
(
u
,
v
)
,
f
(
u
,
v
)
)
=
(
k
−
i
,
k
−
j
)
(
u
,
v
∈
W
k
(
Σ
n
)
)
{\displaystyle u\sim _{i,j}v\iff \left(e(u,v),f(u,v)\right)=(k-i,k-j)\qquad (u,v\in \operatorname {W} _{k}(\Sigma ^{n}))}
를 정의하면,
(
W
k
(
Σ
n
)
,
(
∼
i
,
j
)
i
,
j
)
{\displaystyle (\operatorname {W} _{k}(\Sigma ^{n}),(\sim _{i,j})_{i,j})}
결합 도식 을 이룬다. 이를
Σ
{\displaystyle \Sigma }
존슨 결합 도식
J
|
Σ
|
(
k
,
n
)
{\displaystyle \operatorname {J} _{|\Sigma |}(k,n)}
[1]
q
{\displaystyle q}
J
q
(
k
,
n
)
{\displaystyle \operatorname {J} _{q}(k,n)}
집합의 크기 는 다음과 같다.
|
J
q
(
k
,
n
)
|
=
(
q
−
1
)
k
(
n
k
)
{\displaystyle |\operatorname {J} _{q}(k,n)|=(q-1)^{k}{\binom {n}{k}}}
이진 존슨 결합 도식
J
2
(
k
,
n
)
{\displaystyle \operatorname {J} _{2}(k,n)}
이항 관계 의 수는 (항등 관계를 포함하여)
⌊
n
/
2
⌋
+
1
{\displaystyle \lfloor n/2\rfloor +1}
{
∼
0
,
0
,
∼
1
,
1
,
…
,
∼
⌊
n
/
2
⌋
,
⌊
n
/
2
⌋
}
{\displaystyle \left\{\sim _{0,0},\;\sim _{1,1},\dotsc ,\sim _{\lfloor n/2\rfloor ,\lfloor n/2\rfloor }\right\}}
존슨 결합 도식
J
q
(
k
,
n
)
{\displaystyle \operatorname {J} _{q}(k,n)}
[1] :279, §1
u
∼
i
,
j
v
⟹
d
H
(
u
,
v
)
=
i
+
j
(
u
,
v
∈
J
q
(
k
,
n
)
)
{\displaystyle u\sim _{i,j}v\implies \operatorname {d_{H}} (u,v)=i+j\qquad (u,v\in \operatorname {J} _{q}(k,n))}
증명:
임의의
u
,
v
∈∈
J
q
(
k
,
n
)
{\displaystyle u,v\in \in \operatorname {J} _{q}(k,n)}
e
(
u
,
v
)
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
∙
≠
u
i
=
v
i
}
|
{\displaystyle e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}=v_{i}\}|}
이므로,
k
−
e
(
u
,
v
)
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
∙
≠
u
i
≠
v
i
}
|
{\displaystyle k-e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}\neq v_{i}\}|}
이다. 마찬가지로,
f
(
u
,
v
)
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
u
i
≠
∙
≠
v
i
}
|
{\displaystyle f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}|}
이므로,
k
−
f
(
u
,
v
)
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
∙
=
u
i
≠
v
i
}
|
{\displaystyle k-f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet =u_{i}\neq v_{i}\}|}
이다. 즉,
d
H
(
u
,
v
)
=
|
{
i
∈
{
0
,
…
,
n
−
1
}
:
u
i
≠
v
i
}
|
=
(
k
−
e
(
u
,
v
)
)
+
(
k
−
f
(
u
,
v
)
)
{\displaystyle \operatorname {d_{H}} (u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq v_{i}\}|=(k-e(u,v))+(k-f(u,v))}
이다.
이진 존슨 결합 도식
J
2
(
k
,
n
)
{\displaystyle \operatorname {J} _{2}(k,n)}
p
i
,
j
=
e
i
(
j
)
{\displaystyle p_{i,j}=e_{i}(j)}
q
i
,
j
=
μ
i
v
i
e
i
(
j
)
{\displaystyle q_{i,j}={\frac {\mu _{i}}{v_{i}}}e_{i}(j)}
여기서
μ
i
=
n
−
2
i
+
1
n
−
i
+
1
(
n
i
)
{\displaystyle \mu _{i}={\frac {n-2i+1}{n-i+1}}{\binom {n}{i}}}
e
i
(
x
)
=
∑
j
=
0
i
(
−
)
j
(
x
j
)
(
k
−
x
i
−
j
)
(
n
−
k
−
x
i
−
j
)
(
i
=
0
,
…
,
k
)
∈
Z
[
x
]
{\displaystyle e_{i}(x)=\sum _{j=0}^{i}(-)^{j}{\binom {x}{j}}{\binom {k-x}{i-j}}{\binom {n-k-x}{i-j}}\qquad (i=0,\dotsc ,k)\in \mathbb {Z} [x]}
이며, 다항식열
(
e
i
)
0
≤
i
≤
k
{\displaystyle (e_{i})_{0\leq i\leq k}}
에벌라인 다항식 (Eberlein多項式, 영어 : Eberlein polynomial )이라고 한다.
미국의 수학자 셀머 마틴 존슨(영어 : Selmer Martin Johnson , 1916~1996)이 도입하였다.
![{\displaystyle e_{i}(x)=\sum _{j=0}^{i}(-)^{j}{\binom {x}{j}}{\binom {k-x}{i-j}}{\binom {n-k-x}{i-j}}\qquad (i=0,\dotsc ,k)\in \mathbb {Z} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1e795c5d6d7f6efb93dae9899b891be542c086b)
