조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다.
목걸이[편집]
임의의 집합 가 주어졌다고 하자. 위의 길이 의 문자열 집합 을 생각할 수 있다. 위에는 차 순환군 은 다음과 같이 자연스럽게 작용한다.
보다 일반적으로, 크기 의 정이면체군 은 다음과 같이 자연스럽게 작용한다.
임의의 집합 가 주어졌을 때, 속의 색깔을 갖는, 길이 의 목걸이(영어: necklace)는 위의, 작용에 대한 궤도이다. 속의 색깔을 갖는, 길이 의 팔찌(영어: bracelet)는 위의, 작용에 대한 궤도이다.
비주기적 목걸이(非週期的-, 영어: aperiodic necklace)는 안정자군이 자명군인 목걸이이다. 임의의 목걸이는 비주기적 목걸이의 반복으로 표준적으로 나타낼 수 있다. 즉, 길이 의 목걸이는 의 어떤 약수 에 대하여, 길이 의 비주기적 목걸이의 번 반복으로 나타낼 수 있다.
목걸이와 팔찌의 수는 포여 열거 정리를 사용하여 계산할 수 있다.
목걸이의 수[편집]
개의 색깔을 가질 수 있는, 길이가 인 목걸이의 수는 다음과 같은 다항식렬로 주어진다.
여기서 는 오일러 피 함수이다.
팔찌의 수[편집]
개의 색깔을 가질 수 있는, 길이가 인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
비주기적 목걸이의 수[편집]
개의 색깔을 가질 수 있는, 길이가 인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
이를 목걸이 다항식(-多項式, 영어: necklace polynomial)이라고 한다. 여기서 는 뫼비우스 함수이다. 모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로
이다.
목걸이 다항식의 공식은 다음과 같이 유도할 수 있다. 우선, 은 순환군의 작용에 대한 궤도들의 크기의 합이므로, 다음 공식이 성립한다.
이를 뫼비우스 반전 공식에 따라 풀면 다음과 같다.
특히, 임의의 소수 에 대하여,
이다.
처음 몇 개의 목걸이 다항식은 다음과 같다.
|
|
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
4 |
|
|
|
5 |
|
|
|
6 |
|
|
|
목걸이 다항식 는 다음과 같은 수학 분야에서 등장한다.
- 개의 문자로 구성된 알파벳 위의 길이 의 린던 단어의 수
- 크기 의 집합으로 생성되는 자유 리 대수의, 차수 부분 공간의 차원
- 크기 의 유한체 위의 차 일계수 기약 다항식의 수
- 목걸이 항등식은 원분 항등식(영어: cyclotomic identity)에서 지수로 등장한다.
샤를 폴 나르시스 모로(프랑스어: Charles Paul Narcisse Moreau)가 1872년에 최초로 목걸이의 열거 문제를 연구하였다.[1]
참고 문헌[편집]
외부 링크[편집]
같이 보기[편집]