📂추상대수

번사이드 공식 유도

개요

번사이드 공식은 군의 작용과 등방부분군에 대한 대표적인 응용으로써 조합론을 비롯한 분야에서 즉시 쓰일 수 있다.

공식 ¹

유한군 $G$ 에 대해 유한집합 $X$ 가 $G$-집합이라고 하자. $r$ 이 $G$ 하의 $X$ 의 궤도의 갯수라고 하면 $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

유도

집합 $\left\{ (g,x) \in G \times X | gx = x \right\}$ 의 기수를 $N$ 이라고 하면 $$X_{g} = \left\{ x \in X \ | \ gx = x \right\}$$ 이고, $G_{x} = \left\{ g \in G \ | \ gx = x \right\}$ 에 대해 다음이 성립한다. $$N = \sum_{g \in G} |X_{g}| = \sum_{x \in X} |G_{x}|$$

등방부분군의 성질: $X$ 가 $G$-집합이면 $|Gx| = ( G : G_{x})$ 이다. $G$ 가 유한군이면 $|Gx|$ 는 $|G|$ 의 약수다.

$|G| = |G_{x} | |Gx|$ 이므로 $\displaystyle N = \sum_{x \in X} |G_{x}|$ 에서 $$N = \sum_{x \in X} {{|G|} \over {|Gx|}} = |G| \sum_{x \in X} {{1} \over {|Gx|}}$$ 어떤 궤도 $\mathscr{O}$ 에 대해서는 $x \in \mathscr{O}$ 에 대해 $|Gx|$ 가 모두 같은 값을 가지므로, $$\sum_{x \in \mathscr{O}} {{1} \over {| Gx | }} = 1$$ 이다. 궤도의 갯수는 $r$ 이므로 $N = |G| r$ 이고, 정리하면 다음을 얻는다. $$r |G| = \sum_{g \in G} \left| X_{g} \right|$$

■

예제

원탁 문제

$7$ 명이 원탁에 둘러 앉는 경우의 수를 구하라.

---

$7$ 명을 일렬로 배치하는 경우의 수는 $7!$ 이다.

시계 반대 방향으로 돌려 앉히는 ‘작용’은 총 $7$ 가지다. 따라서 경우의 수는 $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {7}} 7! = 720$$

염주 문제

$7$ 개의 서로 다른 구슬을 실에 꿰는 경우의 수를 구하라.

---

$7$ 구를 일렬로 배치하는 경우의 수는 $7!$ 이다. 시계 반대 방향으로 돌리고 염주를 뒤집는 작용은 총 $7 \times 2 = 14$ 가지다. 따라서 $$r = {{1} \over {|G|}} \sum_{g \in G} | X_{g} | = {{1} \over {14}} 7! = 360$$