목걸이 (조합론)

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

$\backslash mathcal\{B\}$의 모든 구슬로 만들어진다.

여기서 $|\backslash mathcal\{B\}|\; :=\; \backslash sum\backslash limits\_\{i=1\}^k\; n\_i$이고 $\{m\; \backslash choose\; m\_1,\; \backslash ldots,\; m\_k\}$

:= \frac{m!}{m_1! \cdots m_k!} 는 다항 계수이다.

이 두 공식은 집합 $f\; :\; \backslash \{1,\backslash ldots,n\backslash \}\; \backslash to\backslash \{1,\backslash ldots,k\backslash \}$에 작용하는 순환군 $C\_n$의 작용에 적용된 폴리 열거 정리에서 직접적으로 도출된다.

모든 ''k''가지 색상을 사용해야 하는 경우 개수는 다음과 같다.

:$L\_k(n)=\backslash frac\{k!\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)S\backslash left(\backslash frac\{n\}\{d\},\; k\backslash right)\backslash ;,$

여기서 $S(n,\; k)$는 제2종 스털링 수이다.

$N\_k(n)$과 $L\_k(n)$는 이항 계수를 통해 다음과 같이 관련된다.

:$N\_k(n)=\backslash sum\_\{j=1\}^k\backslash binom\{k\}\{j\}\; L\_j(n)$

그리고

:$L\_k(n)=\backslash sum\_\{j=1\}^k(-1)^\{k-j\}\backslash binom\{k\}\{j\}N\_j(n)$

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

:$B\_k(n)\; =\; \backslash 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''진 목걸이의 수는 다음과 같다.^[1]

:$N\_k(n)=\backslash frac\{1\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)k^\{n/d\}\; =\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; k^\{\backslash ,\; \{\backslash rm\; gcd\}(i,\; n)\}$

여기서 $\backslash varphi$는 오일러 피 함수이다.^[1]

이 공식은 폴리아 열거 정리를 순환군 $C\_n$의 작용에 적용하여 유도할 수 있다.^[2]

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

:$L\_k(n)=\backslash frac\{k!\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)S\backslash left(\backslash frac\{n\}\{d\},\; k\backslash right)\backslash ;$

$N\_k(n)$과 $L\_k(n)$는 이항 계수를 통해 서로 연관된다.

3. 2. 팔찌의 수

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

:$B\_n(x)\backslash in\backslash mathbb\; Q[x]$

:

\\ x^{(n+1)/2}/2 & 2\nmid n\end{cases}

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

:$B\_k(n)\; =\; \backslash 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)=\backslash frac\{1\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash mu(d)k^\{n/d\}$

여기서 ''k''는 색깔의 개수, ''n''은 목걸이의 길이이다. 두 목걸이 세기 함수는 뫼비우스 반전 공식에 의해 다음과 같은 관계를 갖는다. $N\_k(n)\; =\; \backslash sum\_\{d|n\}\; M\_k(d),$$M\_k(n)\; =\; \backslash sum\_\{d|n\}\; N\_k(d)\backslash ,\backslash mu\backslash bigl(\backslash tfrac\{n\}\{d\}\backslash bigr).$

'''목걸이 다항식'''(-多項式, necklace polynomial^영어) $M\_n(x)\backslash in\backslash mathbb\; Q[x]$는 다음과 같이 정의된다.

:$M\_n(x)=\backslash frac1n\backslash sum\_\{d\backslash mid\; n\}\backslash mu(n/d)x^d$

모든 목걸이는 비주기적 목걸이로 분해할 수 있으므로, $N\_n(x)=\backslash sum\_\{d\backslash 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$