대칭의 조합
녹색과 검은 색으로 색칠 된 두 개의 다른 선으로 연결된 6 개의 동일한 정점이 있다고 가정 해 봅시다.
이 시스템에서 파티션을 만들 수있는 고유 한 방법 수를 세고 싶습니다. 예를 들어 1x5 파티션을 만들려면
우리가 생각할 수있는 가장 쉬운 방법은 6C1 = 6 케이스입니다. 그러나 시스템은 60도 각도의 회전 대칭을 가지고 있습니다. 따라서 우리는 2 개의 고유 한 파티션 만 갖게됩니다. 색상 순서를 무시하면 고유 한 파티션 이 하나만 있습니다 . 파티션에는 녹색과 검은 색 하나만 저장할 수 있습니다.
3x3 파티션의 경우 조금 더 복잡해집니다. 먼저 총 6C3 = 20 파티션이 존재 함을 알 수 있습니다. 이중 계산을 제거하면 10 개의 케이스 만 있습니다.
그러나 대칭을 고려해야합니다. 나는 손으로 해답을 알고 있으며, 우리는 단지 4 개의 독특한 케이스를 가지고 있습니다. 우리는 (1 (3green and 3 black) +3 (Green + Black) +3 (3black and one green) +3 (3 green and one black).
이 규칙을 사용하여 다음과 같이 고유 한 솔루션을 계산할 수있었습니다.
(4 선택 1) 우리는 1 개의 유일한 케이스가 있습니다
(4 개 선택 2) 우리는 3 개의 독특한 케이스를 가지고 있습니다.
(6 선택 1) 우리는 1 개의 유일한 케이스가 있습니다
(6 개 선택 2) 우리는 4 개의 유일한 케이스가 있습니다
(6 개 3 개 선택) 우리는 4 개의 유일한 케이스가 있습니다
시스템의 대칭과 함께 일반화 된 조합 솔루션을 찾을 수있는 방법이 있습니까?
답변
일부 대칭 (이 경우 회전 대칭)에 대해 다른 세트 (여기서는 육각형)의 파티션 수를 요청합니다. 일반적으로 이것은 수학에서 중요하고 잘 연구 된 질문입니다. 이 예제를 자세히 연구하여이 자료를 접하게되어 기쁩니다.
이 문제를 해결하는 가장 일반적인 방법은 Burnside의 기본형 이라는 것을 사용하는 것 입니다. 더 배우고 싶다면 그룹 이론에 관한 교과서를 찾아보아야합니다.
이 특정 예를 체계적으로 해결하기 위해 그룹 이론 배경을 명시 적으로 필요로하지 않고 Burnside의 기본형에서 아이디어를 사용할 수 있습니다. 예를 들어 다음이 있다는 증거를 다시 말합시다.$4$ 육각형의 구별되는 파티션을 각각 세 점의 두 세트로 만듭니다.
당신은 정확하게 지적했다 $\binom{6}{3} = 20$ 가능한 크기의 하위 집합 $3$, 그래서 있습니다 $\binom{6}{3} / 2 = 10$가능한 파티션. 파티션 용$P$, 허락하다 $f(P)$ 서로 다른 회전 된 사본의 방법 수를 나타냅니다. $P$.
예를 들어, 이미지 (아래 복사)에서 $P$ 왼쪽 상단 파티션이고 $P'$오른쪽 상단 파티션이됩니다. 그때$f(P) = 3$ 과 $f(P') = 1$.
모두의 목록을 고려하십시오 $10$ 파티션 $P_1, \dots, P_{10}$. 각 파티션$P$, 정확히 "초과 계산" $f(P)$타임스. 회전에 대해 다른 각 파티션을 한 번 계산하기 위해 다음 트릭을 수행합니다. 우리는 합계를 고려합니다
$$ \sum_{i=1}^{10} \frac{1}{f(P_i)} .$$
육각형의 칸막이를 크기 3의 두 세트로 찾는 경우 이것은 합이됩니다.
$$ \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + 1 = 4,$$
정확히 당신이 계산 한 것입니다!
이 공식은 육각형을 크기 집합으로 분할하는 경우에도 적용됩니다. $1$ 그리고 크기 세트 $5$. 거기에$6$ 총 파티션, 각 파티션에 대해 $f(P) = 6$(각 파티션은 서로의 회전이기 때문에). 그래서 합계는
$$ \sum_{i=1}^6 \frac{1}{f(P)} = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1.$$
작동 방식이 혼란 스러우면 다른 경우에도이 공식을 사용해보십시오. 육각형을 다른 것으로 대체하는 경우에도 작동합니다.$n$예를 들어 -gon. 어려운 부분은 계산이됩니다$f(P)$ 각 파티션에 대해 $P$(및 가능한 모든 파티션 열거). 질문에 대한 답변이 되었기를 바랍니다.