목걸이 (조합론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

목걸이 (조합론)은 주어진 집합의 색깔을 사용하여 만들어지는 문자열의 순환적 배열인 목걸이, 그리고 이를 뒤집는 경우까지 고려한 팔찌에 대한 조합론적 개념을 다룬다. 목걸이와 팔찌는 순환군과 이항군을 사용하여 정의되며, 폴리아 열거 정리를 통해 그 수를 계산할 수 있다. 비주기적 목걸이는 안정자군이 자명군인 목걸이로, 모로의 목걸이 세기 함수와 뫼비우스 함수를 사용하여 개수를 계산할 수 있다. 목걸이 다항식은 린던 단어, 자유 리 대수, 유한체 위의 기약 다항식 등의 계산에 응용되며, 모로가 1872년에 이 문제를 처음 연구했다.

목걸이 (조합론)

조합론적 목걸이 정보

이미지 준비중입니다.

4개의 구슬로 이루어진 6개의 목걸이

유형	조합론

관련 항목	드 브루인 시퀀스 홀 다항식 위트 벡터 순열 그룹

2. 정의

2.1. 목걸이

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

:a^k: c₀c₁ ⋯ c_n-1 ↦ c_kc_k+1 ⋯ c_n-1c₀ ⋯ c_k-1

집합 C 속의 색깔을 갖는, 길이 n의 목걸이(necklace^영어)는 Cⁿ 위의, Cyc(n) 작용에 대한 궤도이다.

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

2.2. 팔찌

2.3. 비주기적 목걸이

임의의 집합 $C$ 가 주어졌을 때, $C$ 속의 색깔을 갖는, 길이 $n$ 의 목걸이는 $C^n$ 위의, 순환군 $\operatorname{Cyc}(n)$ 작용에 대한 궤도이다.

비주기적 목걸이(非週期的-, aperiodic necklace^영어)는 안정자군이 자명군인 목걸이이다. 즉, 길이 n의 비주기적 목걸이는 크기가 n인 회전 동치류이며, 이러한 류의 목걸이를 회전시킨 두 개의 서로 다른 회전은 같지 않다. 임의의 목걸이는 비주기적 목걸이의 반복으로 표준적으로 나타낼 수 있다. 즉, 길이 $n$ 의 목걸이는 $n$ 의 어떤 약수 $d$ 에 대하여, 길이 $d$ 의 비주기적 목걸이의 $n/d$ 번 반복으로 나타낼 수 있다.

모로의 목걸이 세기 함수에 따르면, k-진 비주기적 목걸이의 길이는 n이고, 여기서 μ는 뫼비우스 함수이다. 각 비주기적 목걸이는 단일 린든 워드를 포함하므로 린든 워드는 비주기적 목걸이의 동치류 대표를 형성한다.

3. 목걸이와 팔찌의 수

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

k진 목걸이는 n개의 구슬에 k가지 색 중 하나를 칠하는 방법이다. 길이 n의 k진 목걸이의 수는 다음과 같다.

: $N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^{n/d} = \frac{1}{n} \sum_{i=1}^n k^{\, {\rm gcd}(i, n)}$

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

이 공식은 폴리아 열거 정리를 순환군 $C_n$ 의 작용에 적용하여 유도할 수 있다.

만약 모든 k가지 색상을 반드시 전부 사용해야 한다면, 목걸이의 개수는 다음과 같이 제2종 스털링 수를 사용하여 표현할 수 있다.

: $L_k(n)=\frac{k!}{n}\sum_{d\mid n}\varphi(d)S\left(\frac{n}{d}, k\right)\;$

$N_k(n)$ 과 $L_k(n)$ 는 이항 계수를 통해 서로 연관된다.

구슬이 특정 색상 멀티셋 $\mathcal{B} = \{1^{n_1},\ldots,k^{n_k} \}$ 로 제한될 때, $n_i$ 는 색상 $i \in \{1,\ldots,k\}$ 의 구슬 수이고, 다음 식을 만족하는 서로 다른 목걸이가 존재한다.

: $N(\mathcal{B}) = \frac{1}$

👆

좌우로 밀어서 보기

\sum_{d | {\rm gcd}(n_1,\ldots,n_k)} {|\mathcal{B}|/d \choose n_{1}/d, \ldots, n_{k}/d} \phi(d)

\mathcal{B}

의 모든 구슬로 만들어진다.
여기서

|\mathcal{B}| := \sum\limits_{i=1}^k n_i

이고

{m \choose m_1, \ldots, m_k}:= \frac{m!}{m_1! \cdots m_k!}

는 다항 계수이다.
이 두 공식은 집합

f : \{1,\ldots,n\} \to\{1,\ldots,k\}

에 작용하는 순환군

C_n

의 작용에 적용된 폴리 열거 정리에서 직접적으로 도출된다.
모든 k가지 색상을 사용해야 하는 경우 개수는 다음과 같다.

:

L_k(n)=\frac{k!}{n}\sum_{d\mid n}\varphi(d)S\left(\frac{n}{d}, k\right)\;,

여기서

S(n, k)

는 제2종 스털링 수이다.

N_k(n)

과

L_k(n)

는 이항 계수를 통해 다음과 같이 관련된다.

:

N_k(n)=\sum_{j=1}^k\binom{k}{j} L_j(n)

그리고

:

L_k(n)=\sum_{j=1}^k(-1)^{k-j}\binom{k}{j}N_j(n)

길이 n인 서로 다른 k-진 팔찌의 개수는 다음과 같다.
:

B_k(n) = \begin{cases}\tfrac12 N_k(n) + \tfrac14 (k+1)k^{n/2} & \text{만약 }n\text{이 짝수} \\[10px]\tfrac12 N_k(n) + \tfrac12 k^{(n+1)/2} & \text{만약 }n\text{이 홀수}\end{cases}\quad,

여기서 N_k(n)은 길이 n인 k-진 목걸이의 개수이다. 이는 이항군

D_n

의 작용에 폴리야의 방법을 적용하여 얻을 수 있다.

3.1. 목걸이의 수

k진 목걸이는 n개의 구슬에 k가지 색 중 하나를 칠하는 방법이다. 길이 n의 k진 목걸이의 수는 다음과 같다.

: $N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^{n/d} = \frac{1}{n} \sum_{i=1}^n k^{\, {\rm gcd}(i, n)}$

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

이 공식은 폴리아 열거 정리를 순환군 $C_n$ 의 작용에 적용하여 유도할 수 있다.

만약 모든 k가지 색상을 반드시 전부 사용해야 한다면, 목걸이의 개수는 다음과 같이 제2종 스털링 수를 사용하여 표현할 수 있다.

: $L_k(n)=\frac{k!}{n}\sum_{d\mid n}\varphi(d)S\left(\frac{n}{d}, k\right)\;$

$N_k(n)$ 과 $L_k(n)$ 는 이항 계수를 통해 서로 연관된다.

3.2. 팔찌의 수

$x$ 개의 색깔을 가질 수 있는, 길이가 $n$ 인 팔찌의 수는 다음과 같은 다항식렬로 주어진다.
: $B_n(x)\in\mathbb Q[x]$
: $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}$
길이 n인 서로 다른 k-진 팔찌의 개수는 다음과 같다.
: $B_k(n) = \begin{cases}\tfrac12 N_k(n) + \tfrac14 (k+1)k^{n/2} & \text{만약 }n\text{이 짝수} \\[10px]\tfrac12 N_k(n) + \tfrac12 k^{(n+1)/2} & \text{만약 }n\text{이 홀수}\end{cases}\quad,$
여기서 $N_k(n)$ 은 길이 n인 k-진 목걸이의 개수이다. 이는 이항군 $D_n$ 의 작용에 폴리야의 방법을 적용하여 얻을 수 있다.

3.3. 서로 다른 구슬로 이루어진 경우

주어진 n개의 구슬 집합에 대해 모든 구슬이 다를 경우, 회전된 목걸이를 동일하게 취급할 때, 이러한 구슬로 만들어진 서로 다른 목걸이의 수는 (n − 1)! 이다. 이는 구슬을 n!가지 방법으로 선형으로 정렬할 수 있고, 이러한 정렬의 n가지 원형 이동이 모두 동일한 목걸이를 만들기 때문이다. 마찬가지로, 회전 및 반사된 팔찌를 동일하게 취급할 때, 서로 다른 팔찌의 수는 n ≥ 3에 대해 이다.

구슬의 색상이 반복되어 모든 구슬이 다르면, 목걸이(및 팔찌)의 수가 줄어든다. 폴리아 열거 정리는 각 구슬 색상에 대한 변수를 사용하여 계산 다항식을 개선하여, 각 단항식의 계수가 주어진 구슬 멀티셋에 대한 목걸이 수를 계산하도록 한다.

3.4. 비주기적 목걸이의 수

뫼비우스 함수(μ)를 이용하여 비주기적 목걸이의 수를 계산하는 공식은 모로의 목걸이 세기 함수를 통해 얻을 수 있다.
: $M_k(n)=\frac{1}{n}\sum_{d\mid n}\mu(d)k^{n/d}$
여기서 k는 색깔의 개수, n은 목걸이의 길이이다. 두 목걸이 세기 함수는 뫼비우스 반전 공식에 의해 다음과 같은 관계를 갖는다. $N_k(n) = \sum_{d|n} M_k(d),$ $M_k(n) = \sum_{d|n} N_k(d)\,\mu\bigl(\tfrac{n}{d}\bigr).$

목걸이 다항식(-多項式, necklace polynomial^영어) $M_n(x)\in\mathbb Q[x]$ 는 다음과 같이 정의된다.
: $M_n(x)=\frac1n\sum_{d\mid n}\mu(n/d)x^d$
모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로, $N_n(x)=\sum_{d\mid n}M_d(x)$ 이다. 이는 뫼비우스 반전 공식을 통해 유도할 수 있다.

길이 n의 비주기적 목걸이는 크기가 n인 회전 동치류이며, 이러한 류의 목걸이를 회전시켰을 때 서로 다른 회전은 같지 않다. 각 비주기적 목걸이는 단일 린든 워드를 포함하므로 린든 워드는 비주기적 목걸이의 동치류 대표를 형성한다.

4. 표

wikitable

👆

좌우로 밀어서 보기

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$

5. 응용

목걸이 다항식 $M_n(x)$ 는 다음과 같은 수학 분야에서 등장한다.
* $x$ 개의 문자로 구성된 알파벳 위의 길이 $n$ 의 린던 단어(Lyndon word)의 수
* 크기 $x$ 의 집합으로 생성되는 자유 리 대수(Free Lie algebra)의, 차수 $n$ 부분 공간의 차원
* 크기 $x=p^k$ 의 유한체(Finite field) 위의 $n$ 차 일계수 기약 다항식(Irreducible polynomial)의 수
* 목걸이 항등식은 원분 항등식(Cyclotomic identity)에서 지수로 등장한다.

6. 역사

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