해밍 결합 도식

조합론에서 해밍 결합 도식(Hamming結合圖式, )은 해밍 거리가 주어진 곱집합으로 구성된 결합 도식이다.

 정의 
 해밍 거리를 통한 정의 
다음 데이터가 주어졌다고 하자.
 유한 집합 
 자연수 
그렇다면, 곱집합  위에 다음과 같은 이항 관계 들을 주자.

여기서
 은 해밍 거리이다.
그렇다면, 은 결합 도식을 이룬다. 이를 -해밍 결합 도식이라고 한다.

 군 작용을 통한 정의 
해밍 결합 도식은 대신 군의 작용을 통해 정의될 수도 있다.

구체적으로, 곱집합 이 주어졌을 때, 다음과 같은 두 단사 군 준동형을 생각할 수 있다.

여기서
 는 의 원소의 개의 성분들 사이의 순열을 취하는 것이다.
 는 의 원소의 개의 성분들에 각각 순열을 가하는 것이다.
의 상은 의 정규 부분군이며, 분할 완전열

이 존재한다. 그렇다면, 와 의 상으로 생성되는, 대칭군 의 부분군을 생각할 수 있으며, 이는 과 의 반직접곱

이다.

그렇다면,  위에 의 성분별 작용

을 가했을 때, 그 궤도들은  위의 결합 도식을 정의하며, 이를 해밍 결합 도식이라고 한다.

 일반화 해밍 결합 도식 
다음 데이터가 주어졌다고 하자.
 결합 도식 
 자연수 
그렇다면, 곱집합 의 임의의 두 원소 에 대하여,

를 정의하자. 그렇다면,

이다. 이제, 가
 개의 성분을 가지며,
 모든 성분이 0 또는 1이며,
 모든 성분의 합이 인
벡터들의 집합이라고 하자. 그렇다면,  위에 각 에 대하여

를 주면, 이는 결합 도식을 이룬다. 이를  위의 차 일반화 해밍 결합 도식()이라고 한다.

 성질 
해밍 결합 도식은 대칭 결합 도식이다. 즉, 그 모든 이항 관계는 대칭 관계이다.

 대수적 성질 
해밍 결합 도식 의 인접 행렬들이 라고 하자.

해밍 결합 도식의 구조 상수는 다음과 같다.

특히, 일 때 이는 인 항만 남게 되며, 이 경우 구조 상수는 다음과 같다.

그렇다면, 해밍 결합 도식의 복소수 계수 보스-메스너 대수의 최소 멱등원들은 다음과 같다.

여기서

는 크라우추크 다항식(Кравчук多項式, )이다.

또한, 다음이 성립한다.

여기서  및 이 같은 것은 해밍 결합 도식이 스스로의 쌍대이기 때문이다.

 예 
(2,2)-해밍 결합 도식은 다음과 같다.
  AA  AB  BA  BB AA 0  1  1  2 AB 1  0  2  1 BA 1  2  0  1 BB 2  1  1  0

 역사 
“해밍 결합 도식”이라는 용어는 리처드 해밍의 이름을 땄으며, 해밍 거리에서 유래하였다.

크라우추크 다항식은 우크라이나의 수학자 미하일로 필리포비치 크라우추크(, , 1892~1942)가 도입하였다.

 참고 문헌 

 외부 링크 





분류:조합론
분류:부호 이론