목걸이 (조합론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''목걸이'''({{llang|en|necklace}})는 [[순환군]]의 [[군의 작용|작용]]에 대한 [[문자열]]의 궤도이다.

== 정의 ==
=== 목걸이 ===
임의의 [[집합]] <math>C</math>가 주어졌다고 하자. <math>C</math> 위의 길이 <math>n</math>의 [[문자열]] 집합 <math>C^n</math>을 생각할 수 있다. <math>C^n</math> 위에는 <math>n</math>차 [[순환군]] <math>\operatorname{Cyc}(n)=\langle a|a^n=1\rangle</math>은 다음과 같이 자연스럽게 [[군의 작용|작용]]한다.
:<math>a^k\colon c_0c_1\cdots c_{n-1}\mapsto c_kc_{k+1}\cdots c_{n-1}c_0\cdots c_{k-1}</math>
보다 일반적으로, 크기 <math>2n</math>의 [[정이면체군]] <math>\operatorname{Dih}(n)=\langle a,b|a^n=b^2=1,\;(ba)^2=1\rangle</math>은 다음과 같이 자연스럽게 작용한다.
:<math>a^k\colon c_0c_1\cdots c_{n-1}\mapsto c_kc_{k+1}\cdots c_{n-1}c_0\cdots c_{k-1}</math>
:<math>b\colon c_0c_1\cdots c_{n-1}\mapsto c_{n-1}\cdots c_1c_0</math>

임의의 [[집합]] <math>C</math>가 주어졌을 때, <math>C</math> 속의 색깔을 갖는, 길이 <math>n</math>의 '''목걸이'''({{llang|en|necklace}})는 <math>C^n</math> 위의, <math>\operatorname{Cyc}(n)</math> 작용에 대한 [[군의 작용|궤도]]이다. <math>C</math> 속의 색깔을 갖는, 길이 <math>n</math>의 '''팔찌'''({{llang|en|bracelet}})는 <math>C^n</math> 위의, <math>\operatorname{Dih}(n)</math> 작용에 대한 [[군의 작용|궤도]]이다.

'''비주기적 목걸이'''(非週期的-, {{llang|en|aperiodic necklace}})는 [[안정자군]]이 [[자명군]]인 목걸이이다. 임의의 목걸이는 비주기적 목걸이의 반복으로 표준적으로 나타낼 수 있다. 즉, 길이 <math>n</math>의 목걸이는 <math>n</math>의 어떤 약수 <math>d</math>에 대하여, 길이 <math>d</math>의 비주기적 목걸이의 <math>n/d</math>번 반복으로 나타낼 수 있다.

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

=== 목걸이의 수 ===
<math>x</math>개의 색깔을 가질 수 있는, 길이가 <math>n</math>인 목걸이의 수는 다음과 같은 다항식렬로 주어진다.
:<math>N_n(x)\in\mathbb Q[x]</math>
:<math>N_n(x)=\frac1n\sum_{d\mid n}\varphi(n/d)x^d</math>
여기서 <math>\varphi</math>는 [[오일러 피 함수]]이다.

=== 팔찌의 수 ===
<math>x</math>개의 색깔을 가질 수 있는, 길이가 <math>n</math>인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
:<math>B_n(x)\in\mathbb Q[x]</math>
:<math>B_n(x)=\frac12N_n(x)+\begin{cases}(x+1)x^{n/2}/4 & 2\mid n\\
\\ x^{(n+1)/2}/2 & 2\nmid n\end{cases}</math>

=== 비주기적 목걸이의 수 ===
<math>x</math>개의 색깔을 가질 수 있는, 길이가 <math>n</math>인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
:<math>M_n(x)\in\mathbb Q[x]</math>
:<math>M_n(x)=\frac1n\sum_{d\mid n}\mu(n/d)x^d</math>
이를 '''목걸이 다항식'''(-多項式, {{llang|en|necklace polynomial}})이라고 한다. 여기서 <math>\mu</math>는 [[뫼비우스 함수]]이다. 모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로
:<math>N_n(x)=\sum_{d\mid n}M_d(x)</math>
이다.

목걸이 다항식의 공식은 다음과 같이 유도할 수 있다. 우선, <math>x^n</math>은 순환군의 작용에 대한 궤도들의 크기의 합이므로, 다음 공식이 성립한다.
:<math>x^n=\sum_{d\mid n}dM_d(x)</math>
이를 [[뫼비우스 반전 공식]]에 따라 풀면 다음과 같다.
:<math>M_n(x)=\frac1n\sum_{d\mid n}\mu(n/d)x^d</math>
특히, 임의의 [[소수 (수론)|소수]] <math>p</math>에 대하여,
:<math>M_{p^n}(x)=p^{-n}\left(x^{p^n}-x^{p^{n-1}}\right)</math>
이다.

== 표 ==
처음 몇 개의 목걸이 다항식은 다음과 같다.
{| class="wikitable"
|-
! <math>n</math> !! <math>N_n(x)</math> !! <math>B_n(x)</math> !! <math>M_n(x)</math>
|-
| 1 || <math>x</math> || <math>x</math> || <math>x</math>
|-
| 2 || <math>(x^2+x)/2</math> || <math>(x^2+x^2+2x)/4</math> || <math>(x^2-x)/2</math>
|-
| 3 ||  <math>(x^3+2x)/3</math> || <math>(x^3+3x^2+2x)/6</math> || <math>(x^3-x)/3</math>
|-
| 4 || <math>(x^4+x^2+2x)/4</math> || <math>(x^4+2x^3+3x^2+2x)/8</math> || <math>(x^4-x^2)/4</math>
|-
| 5 || <math>(x^5+4x)/5</math> ||  <math>(x^5+5x^3+4x)/10</math> || <math>(x^5-x)/5</math>
|-
| 6 || <math>(x^6+x^3+2x^2+2x)/6</math> || <math>(x^6+3x^4+4x^3+2x^2+2x)/12</math> || <math>(x^6-x^3-x^2+x)/6</math>
|}

== 응용 ==
목걸이 다항식 <math>M_n(x)</math>는 다음과 같은 수학 분야에서 등장한다.
* <math>x</math>개의 문자로 구성된 알파벳 위의 길이 <math>n</math>의 [[린던 단어]]의 수
* 크기 <math>x</math>의 [[집합]]으로 생성되는 [[자유 리 대수]]의, 차수 <math>n</math> 부분 공간의 차원
* 크기 <math>x=p^k</math>의 [[유한체]] 위의 <math>n</math>차 [[일계수 다항식|일계수]] [[기약 다항식]]의 수
* 목걸이 항등식은 [[원분 항등식]]({{llang|en|cyclotomic identity}})에서 지수로 등장한다.

== 역사 ==
샤를 폴 나르시스 모로({{llang|fr|Charles Paul Narcisse Moreau}})가 1872년에 최초로 목걸이의 열거 문제를 연구하였다.<ref>{{저널 인용 | last1=Moreau | first1=C.  | title=Sur les permutations circulaires distinctes | url=http://www.numdam.org/item?id=NAM_1872_2_11__309_0 | 언어=fr | jfm=04.0086.01 | 날짜=1872 | journal=Nouvelles annales de mathématiques | volume=11 | pages=309–314 }}</ref>

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=Necklace|title=Necklace}}

== 같이 보기 ==
* [[포여 열거 정리]]

[[분류:열거조합론]]