조합론에서 존슨 결합 도식(Johnson結合圖式, 영어: Johnson scheme)은 주어진 해밍 무게의 벡터들로 구성된, 2진 해밍 결합 도식의 부분 결합 도식이다.
다음이 주어졌다고 하자.
- 크기
의 유한 집합 ![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
- 자연수
![{\displaystyle k\leq n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/621f658bb51d7caac329d29e9bf435361813777f)
그렇다면, 다음을 정의하자.
는
의, 크기
의 부분 집합들의 집합족이다.
- 각
및
에 대하여, 이항 관계
(여기서
는 해밍 거리)
그렇다면,
는 결합 도식을 이루며, 이를
-이진 존슨 결합 도식(영어: binary Johnson association scheme)
이라고 한다.
진 존슨 결합 도식 (
)
[편집]
다음이 주어졌다고 하자.
- 유한 점을 가진 집합
(
). 이에 따라,
에 대하여 해밍 무게를 정의할 수 있다.
- 두 양의 정수
![{\displaystyle 0<k\leq n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/286189164be6c81f65c95cc3b2d29baed80e56c3)
그렇다면, 다음과 같은 두 함수를 정의할 수 있다.
![{\displaystyle e,f\colon \Sigma ^{n}\times \Sigma ^{n}\to \{0,1,\dotsc ,n\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/032434e43eac0a6e6fd0b6dc0ce98373784d8f29)
![{\displaystyle e\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}=v_{i}\neq \bullet \}\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4ebf1f060f3781c2035e46fcf8579cd2136919b)
![{\displaystyle f\colon (u,v)\mapsto \left|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95faa319f0da373e98bf718a7d9114effcd51bac)
(만약
라면,
이다.)
이제,
에 대한 해밍 무게가
인 길이
의
-문자열들의 집합
![{\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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af05920a45f6df46d786db69269da74593d219b1)
을 생각하자. 이 위에, 이항 관계
![{\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}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29b215ddd846f5bf47937b0ebd9bd30e9fb9d697)
를 정의하면,
는 결합 도식을 이룬다. 이를
위의 존슨 결합 도식
이라고 한다.[1]
진 존슨 결합 도식
은 대칭 결합 도식이며, 그 집합의 크기는 다음과 같다.
![{\displaystyle |\operatorname {J} _{q}(k,n)|=(q-1)^{k}{\binom {n}{k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9848c01f0cda5bab48ffe44415650976e468abeb)
이진 존슨 결합 도식
의 이항 관계의 수는 (항등 관계를 포함하여)
개이며, 다음과 같다.
![{\displaystyle \left\{\sim _{0,0},\;\sim _{1,1},\dotsc ,\sim _{\lfloor n/2\rfloor ,\lfloor n/2\rfloor }\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91b8fdab090dd431782d2dedc85d928a36583ece)
존슨 결합 도식
에서, 다음이 성립한다.[1]:279, §1
![{\displaystyle u\sim _{i,j}v\implies \operatorname {d_{H}} (u,v)=i+j\qquad (u,v\in \operatorname {J} _{q}(k,n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3973f014bfb807197465cd38a232ee2eabd0f61)
증명:
임의의
에 대하여,
![{\displaystyle e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}=v_{i}\}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/044c69a5aae6ea7379c8914b633f6c7c25a920c2)
이므로,
![{\displaystyle k-e(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet \neq u_{i}\neq v_{i}\}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/203634f2ef8c8de0d39eeda941fcfa2e3da85d2b)
이다. 마찬가지로,
![{\displaystyle f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon u_{i}\neq \bullet \neq v_{i}\}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33b6d5dfea673214f7146011e8336e7588802968)
이므로,
![{\displaystyle k-f(u,v)=|\{i\in \{0,\dotsc ,n-1\}\colon \bullet =u_{i}\neq v_{i}\}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fee8e94f9b95caebfd17f65ac92a2724d69a5de8)
이다. 즉,
![{\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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ccfcac51424ae1ae29e65deadf7f5101df13b30)
이다.
이진 존슨 결합 도식
의 고윳값들은 다음과 같다.
![{\displaystyle p_{i,j}=e_{i}(j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d0aaf863f5da6091d100f58ed17a8ccca862034)
![{\displaystyle q_{i,j}={\frac {\mu _{i}}{v_{i}}}e_{i}(j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15441c2ff9565e45fb5ab9afac807032e90f926f)
여기서
![{\displaystyle \mu _{i}={\frac {n-2i+1}{n-i+1}}{\binom {n}{i}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da23008879a820172c629cb7ac6e83b321393255)
![{\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)
이며, 다항식열
를 에벌라인 다항식(Eberlein多項式, 영어: Eberlein polynomial)이라고 한다.
미국의 수학자 셀머 마틴 존슨(영어: Selmer Martin Johnson, 1916~1996)이 도입하였다.