조합론에서 목걸이(영어: necklace)는 순환군의 작용에 대한 문자열의 궤도이다.
목걸이[편집]
임의의 집합
가 주어졌다고 하자.
위의 길이
의 문자열 집합
을 생각할 수 있다.
위에는
차 순환군
은 다음과 같이 자연스럽게 작용한다.
![{\displaystyle a^{k}\colon c_{0}c_{1}\cdots c_{n-1}\mapsto c_{k}c_{k+1}\cdots c_{n-1}c_{0}\cdots c_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/453c3ec71e22d6a01b788645c64d4f8fb9241989)
보다 일반적으로, 크기
의 정이면체군
은 다음과 같이 자연스럽게 작용한다.
![{\displaystyle a^{k}\colon c_{0}c_{1}\cdots c_{n-1}\mapsto c_{k}c_{k+1}\cdots c_{n-1}c_{0}\cdots c_{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/453c3ec71e22d6a01b788645c64d4f8fb9241989)
![{\displaystyle b\colon c_{0}c_{1}\cdots c_{n-1}\mapsto c_{n-1}\cdots c_{1}c_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26e9df3573175529faf6c32ef277ad6ee0a5be9e)
임의의 집합
가 주어졌을 때,
속의 색깔을 갖는, 길이
의 목걸이(영어: necklace)는
위의,
작용에 대한 궤도이다.
속의 색깔을 갖는, 길이
의 팔찌(영어: bracelet)는
위의,
작용에 대한 궤도이다.
비주기적 목걸이(非週期的-, 영어: aperiodic necklace)는 안정자군이 자명군인 목걸이이다. 임의의 목걸이는 비주기적 목걸이의 반복으로 표준적으로 나타낼 수 있다. 즉, 길이
의 목걸이는
의 어떤 약수
에 대하여, 길이
의 비주기적 목걸이의
번 반복으로 나타낼 수 있다.
목걸이와 팔찌의 수는 포여 열거 정리를 사용하여 계산할 수 있다.
목걸이의 수[편집]
개의 색깔을 가질 수 있는, 길이가
인 목걸이의 수는 다음과 같은 다항식렬로 주어진다.
![{\displaystyle N_{n}(x)\in \mathbb {Q} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09a92ff43a5166674a116ea8eee03a547a0fba2b)
![{\displaystyle N_{n}(x)={\frac {1}{n}}\sum _{d\mid n}\varphi (n/d)x^{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f885694671ce708f99a490f22b1b56fc9b2c3a0)
여기서
는 오일러 피 함수이다.
팔찌의 수[편집]
개의 색깔을 가질 수 있는, 길이가
인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
![{\displaystyle B_{n}(x)\in \mathbb {Q} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/596acc3ad4007259bde9acf01ab50fc2284bfc53)
![{\displaystyle B_{n}(x)={\frac {1}{2}}N_{n}(x)+{\begin{cases}(x+1)x^{n/2}/4&2\mid n\\\\x^{(n+1)/2}/2&2\nmid n\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/884c53f2047c2fbefb2e7a7a3baaf458066545a5)
비주기적 목걸이의 수[편집]
개의 색깔을 가질 수 있는, 길이가
인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
![{\displaystyle M_{n}(x)\in \mathbb {Q} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/089063b0d199caf2a93891dd4c725ca7b234b6f5)
![{\displaystyle M_{n}(x)={\frac {1}{n}}\sum _{d\mid n}\mu (n/d)x^{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17d8099a0bd1794a90063429b4fa2d4161d0c506)
이를 목걸이 다항식(-多項式, 영어: necklace polynomial)이라고 한다. 여기서
는 뫼비우스 함수이다. 모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로
![{\displaystyle N_{n}(x)=\sum _{d\mid n}M_{d}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ccf29a733154ca642a7edcecbf011178e9f454d)
이다.
목걸이 다항식의 공식은 다음과 같이 유도할 수 있다. 우선,
은 순환군의 작용에 대한 궤도들의 크기의 합이므로, 다음 공식이 성립한다.
![{\displaystyle x^{n}=\sum _{d\mid n}dM_{d}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d71698b0351761e575a00f28dbc90f3a66cf3e08)
이를 뫼비우스 반전 공식에 따라 풀면 다음과 같다.
![{\displaystyle M_{n}(x)={\frac {1}{n}}\sum _{d\mid n}\mu (n/d)x^{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17d8099a0bd1794a90063429b4fa2d4161d0c506)
특히, 임의의 소수
에 대하여,
![{\displaystyle M_{p^{n}}(x)=p^{-n}\left(x^{p^{n}}-x^{p^{n-1}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e272afaf679b970a46ab17c914cfb99d6616eb9c)
이다.
처음 몇 개의 목걸이 다항식은 다음과 같다.
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b) |
![{\displaystyle N_{n}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97629ae0103e9c5435b4e8d0a88d4131c9c50e24) |
![{\displaystyle B_{n}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9192cc7ff70d2e7aff04305da16f00c76a42e1bd) |
|
1 |
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) |
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) |
|
2 |
![{\displaystyle (x^{2}+x)/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4321dc308091d1409a90a3f1a25000d8ff93c1f) |
![{\displaystyle (x^{2}+x^{2}+2x)/4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9428c2e45081730ed149dc839480d61ba713790d) |
|
3 |
![{\displaystyle (x^{3}+2x)/3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/603fe07225b694a1ad79ddc3a6b55a93fc8660a3) |
![{\displaystyle (x^{3}+3x^{2}+2x)/6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a7415d8d2fa3f93c93fcf83e988611308997141) |
|
4 |
![{\displaystyle (x^{4}+x^{2}+2x)/4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c342155e9d5c07a3bdd8d7f3960f04b37fa23c17) |
![{\displaystyle (x^{4}+2x^{3}+3x^{2}+2x)/8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1242210171fd4ff6f19d4b0b28e77bea7e9e8de8) |
|
5 |
![{\displaystyle (x^{5}+4x)/5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be5880a6fcc590e54aac92e7042bf9b342fd2fc9) |
![{\displaystyle (x^{5}+5x^{3}+4x)/10}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2cf15514f4e623987ceee608d8b4ade90ffba9e) |
|
6 |
![{\displaystyle (x^{6}+x^{3}+2x^{2}+2x)/6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26bf7b5c52db8fb5bfd3dc02b09d214db60eb137) |
![{\displaystyle (x^{6}+3x^{4}+4x^{3}+2x^{2}+2x)/12}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a8fcacde0bb83cf4884a0442f258279e023e1a6) |
|
목걸이 다항식
는 다음과 같은 수학 분야에서 등장한다.
개의 문자로 구성된 알파벳 위의 길이
의 린던 단어의 수
- 크기
의 집합으로 생성되는 자유 리 대수의, 차수
부분 공간의 차원
- 크기
의 유한체 위의
차 일계수 기약 다항식의 수
- 목걸이 항등식은 원분 항등식(영어: cyclotomic identity)에서 지수로 등장한다.
샤를 폴 나르시스 모로(프랑스어: Charles Paul Narcisse Moreau)가 1872년에 최초로 목걸이의 열거 문제를 연구하였다.[1]
참고 문헌[편집]
외부 링크[편집]
같이 보기[편집]