목걸이 (조합론)

조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다.

정의

목걸이

임의의 집합 $C$가 주어졌다고 하자. $C$ 위의 길이 $n$의 문자열 집합 $C^n$을 생각할 수 있다. $C^n$ 위에는 $n$차 순환군 $\mathrm{Cyc}(n)=⟨a|a^n=1⟩$은 다음과 같이 자연스럽게 작용한다.

$a^k:c_0{c}_1\cdots c_{n-1}\mapsto c_k{c}_{k+1}\cdots c_{n-1}{c}_0\cdots c_{k-1}$

보다 일반적으로, 크기 $2n$의 정이면체군 $\mathrm{Dih}(n)=⟨a,b|a^n=b^2=1,(ba{)}^2=1⟩$은 다음과 같이 자연스럽게 작용한다.

$a^k:c_0{c}_1\cdots c_{n-1}\mapsto c_k{c}_{k+1}\cdots c_{n-1}{c}_0\cdots c_{k-1}$

$b:c_0{c}_1\cdots c_{n-1}\mapsto c_{n-1}\cdots c_1{c}_0$

임의의 집합 $C$가 주어졌을 때, $C$ 속의 색깔을 갖는, 길이 $n$의 목걸이(영어: necklace)는 $C^n$ 위의, $\mathrm{Cyc}(n)$ 작용에 대한 궤도이다. $C$ 속의 색깔을 갖는, 길이 $n$의 팔찌(영어: bracelet)는 $C^n$ 위의, $\mathrm{Dih}(n)$ 작용에 대한 궤도이다.

비주기적 목걸이(非週期的-, 영어: aperiodic necklace)는 안정자군이 자명군인 목걸이이다. 임의의 목걸이는 비주기적 목걸이의 반복으로 표준적으로 나타낼 수 있다. 즉, 길이 $n$의 목걸이는 $n$의 어떤 약수 $d$에 대하여, 길이 $d$의 비주기적 목걸이의 $n/d$번 반복으로 나타낼 수 있다.

성질

목걸이와 팔찌의 수는 포여 열거 정리를 사용하여 계산할 수 있다.

목걸이의 수

$x$개의 색깔을 가질 수 있는, 길이가 $n$인 목걸이의 수는 다음과 같은 다항식렬로 주어진다.

$N_n(x)\in \mathbb{Q}[x]$

$N_n(x)=\frac{1}{n}\sum _{d\mid n}\phi (n/d)x^d$

여기서 $\phi$는 오일러 피 함수이다.

팔찌의 수

$x$개의 색깔을 가질 수 있는, 길이가 $n$인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.

$B_n(x)\in \mathbb{Q}[x]$

$B_n(x)=\frac{1}{2}{N}_n(x)+\{\begin{array}{cc}(x+1)x^{n/2}/4& 2\mid n\\ \\ x^{(n+1)/2}/2& 2\nmid n\end{array}$

비주기적 목걸이의 수

$x$개의 색깔을 가질 수 있는, 길이가 $n$인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.

$M_n(x)\in \mathbb{Q}[x]$

$M_n(x)=\frac{1}{n}\sum _{d\mid n}\mu (n/d)x^d$

이를 목걸이 다항식(-多項式, 영어: necklace polynomial)이라고 한다. 여기서 $\mu$는 뫼비우스 함수이다. 모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로

$N_n(x)=\sum _{d\mid n}{M}_d(x)$

이다.

목걸이 다항식의 공식은 다음과 같이 유도할 수 있다. 우선, $x^n$은 순환군의 작용에 대한 궤도들의 크기의 합이므로, 다음 공식이 성립한다.

$x^n=\sum _{d\mid n}d{M}_d(x)$

이를 뫼비우스 반전 공식에 따라 풀면 다음과 같다.

$M_n(x)=\frac{1}{n}\sum _{d\mid n}\mu (n/d)x^d$

특히, 임의의 소수 $p$에 대하여,

$M_{p^n}(x)=p^{-n}(x^{p^n}-x^{p^{n-1}})$

이다.

표

처음 몇 개의 목걸이 다항식은 다음과 같다.

$n$	$N_n(x)$	$B_n(x)$	$M_n(x)$
1	$x$	$x$	$x$
2	$(x^2+x)/2$	$(x^2+x^2+2x)/4$	$(x^2-x)/2$
3	$(x^3+2x)/3$	$(x^3+3x^2+2x)/6$	$(x^3-x)/3$
4	$(x^4+x^2+2x)/4$	$(x^4+2x^3+3x^2+2x)/8$	$(x^4-x^2)/4$
5	$(x^5+4x)/5$	$(x^5+5x^3+4x)/10$	$(x^5-x)/5$
6	$(x^6+x^3+2x^2+2x)/6$	$(x^6+3x^4+4x^3+2x^2+2x)/12$	$(x^6-x^3-x^2+x)/6$

응용

목걸이 다항식 $M_n(x)$는 다음과 같은 수학 분야에서 등장한다.

• $x$개의 문자로 구성된 알파벳 위의 길이 $n$의 린던 단어의 수
• 크기 $x$의 집합으로 생성되는 자유 리 대수의, 차수 $n$ 부분 공간의 차원
• 크기 $x=p^k$의 유한체 위의 $n$차 일계수 기약 다항식의 수
• 목걸이 항등식은 원분 항등식(영어: cyclotomic identity)에서 지수로 등장한다.

역사

샤를 폴 나르시스 모로(프랑스어: Charles Paul Narcisse Moreau)가 1872년에 최초로 목걸이의 열거 문제를 연구하였다.

외부 링크

• Weisstein, Eric Wolfgang. “Necklace” (영어). 《Wolfram MathWorld》. Wolfram Research. 

같이 보기

• 포여 열거 정리