경우의 수를 다시 쓴다 (1)

자연과학

Engivia 2025. 4. 22. 00:45

우리는 경우의 수 문제를 풀 때마다 선택을 하고 그 선택들의 수를 세어왔다. 하지만 조금만 깊게 생각해본다.

"같다"는 건 도대체 무엇일까.

A-B-C와 C-A-B는 정말 다른 것인가. 이 색칠 배열과 저 배열은 정말 다른 것인가. 원탁에 앉은 이 배치와 저 배치는 구분할 수 있는 것인가.

문제마다 "같다"는 기준이 달랐다. 수학은 이 모호함을 그냥 둘 수 없었다. 그래서 '군의 작용'이라는 개념을 만들어냈다.

1. 우리는 늘 '같은 것'을 하나로 세고 있다

경우의 수를 셀 때 가장 먼저 하는 일은 구별이다. 그런데 진짜 중요한 것은 어디까지 구별하고 어디서부터 하나로 묶을지를 정하는 일이다.

무엇을 다른 것으로 보고 무엇을 같은 것으로 볼 것인가. 이 기준이 정해지지 않으면 제대로 셀 수 없다.

2. 군의 작용 — '같다'는 기준을 수학적으로 표현하는 방법

수학은 이 문제를 군(group)이라는 개념으로 다룬다. 군이란 여러 가지 변환 규칙들의 모임이다. 이 군이 어떤 집합 위에 작용하면 그 작용을 통해 "같다"는 것을 정의할 수 있다.

예를 들어 보자.

6개의 구슬을 원형으로 배열한다. 시계 방향으로 한 칸 돌린다. 이 돌리는 행동은 '회전 군 C₆'의 작용이다.

여기서 '군의 작용'이란 집합의 원소에 군의 원소를 적용해서 다른 원소로 보내는 규칙을 의미한다.

이제 어떤 배열 A가 있을 때 시계 방향으로 한 칸 돌려서 B가 된다면 A와 B는 같은 것으로 본다.

즉 군의 작용은 "무엇을 같은 것으로 볼 것인가"를 수학적으로 정하는 도구이다.

3. 궤도(orbit) — 우리가 진짜 세야 하는 것

어떤 원소 x가 있을 때 그 위에 군의 모든 작용을 적용해서 나오는 결과들의 집합을 궤도라고 부른다.

Orb(x) = {g ⋅ x | g ∈ G}

쉽게 말해 x를 변형해서 얻을 수 있는 모든 결과들의 집합이다.

우리가 경우의 수를 셀 때 진짜로 세야 하는 것은 원소 하나하나가 아니라 이 궤도들의 개수이다.

4. Burnside's Lemma — 궤도의 수를 세는 방법

그렇다면 군의 작용이 주어졌을 때 궤도의 개수를 어떻게 구할까.

수학은 Burnside의 보조정리라는 간명한 답을 준다.

서로 다른 경우의 수 = (1 / |G|) × ∑ Fix(g)

여기서

|G|는 군의 크기 Fix(g)는 군의 원소 g가 적용되었을 때 변하지 않는 경우의 수를 의미한다.

쉽게 말하면 각 변환이 얼만큼의 배열을 그대로 고정시키는지를 다 더해서 전체 군의 크기로 나눈 것이다.

모든 변환을 평균 내는 셈이다.

5. 예시 — 구슬 목걸이 색칠 문제

구슬 6개를 두 가지 색(흑, 백)으로 칠한다고 하자. 회전으로 같은 배열은 하나로 본다.

처음 생각하면 가능한 배열은 2⁶ = 64가지이다.

하지만 회전을 고려하면 겉모양은 달라도 본질은 같은 배열이 생긴다.

이제 각 회전별로 Fix(g)를 계산해본다.

Fix 합계는 64 + 2 + 8 + 4 + 8 + 2 = 88이다.

이제 88 ÷ 6 = 14.666...이 나오는데 배열이 완전히 균등하게 나눠지지 않는 이유는 회전군의 작용이 모든 배열을 똑같이 다루지 않기 때문이다.

여기서 우리는 알게 된다. 모든 나눗셈이 깔끔히 떨어지는 게 아니다. 회전이나 대칭에 따라 고정되는 배열의 수가 달라지기 때문이다.

6. 모든 경우의 수는 궤도 세기이다

우리가 무심코 했던 나누기 3! 나누기 2! 나누기 n! 이 모든 것은 사실 궤도를 세는 과정이었다.

조편성 문제에서는 조 이름을 무시하는 순열을 하나로 본 것이고 중복 문자 배열에서는 같은 문자의 자리바꿈을 무시한 것이며 원순열 문제에서는 회전을 통한 배열을 하나로 본 것이었다.

항상 묻자. 이 문제에서는 무엇을 같은 것으로 보는가.

그 판단이 서야 군 G가 정해지고 그 위에서 작용이 정의되며 그에 따라 궤도가 정의된다.

- 다음 편에 이어서 -