글
앞에서, 100원짜리 n개와 500원짜리 m개로 1000000원을 지불하는 방법의 수가 몇가지인가를 물어봤었다. 일단 이 문제를 잘 풀어보자. (사실 앞에서 "물리"에 들어가 있던 "마법의 분배함수"글과 내용이 겹친다.)
어쨌든, 500원짜리로 1000000원을 만들기 위해서는 2000개가 필요하다. 그럼, 500원짜리 m개가 있으면, 100원은 몇개나 필요할까?
간단한 산수를 해보면 n=(100000-500m)/100 이다. 아무튼, 중요한건 n개와 m개가 있다는 것이다.
n개와 m개를 모두 합쳐서, 전체를 늘어놓는 방법의 수는 무려 (n+m)!개이다. 하지만, 그중에 n개가 중복된다. n개 끼리는 서로 바꾸더라도 상관이 없기 때문에, n개끼리 서로 바꾸는 경우의 수는 세면 안된다. 반대로 m개도 서로 중복된다. 따라서, 이 경우의 수도 세면 안된다. 잘 생각해 보면, 그런 경우의 수를 세지 않기 위해서는 각 경우의 수로 나눠 줘야 한다는 걸 알 수 있다.
즉, (n+m)! / (n! m!) 가지의 경우가 있다. (이게 왜 맞는지는 100원짜리 2개, 500원짜리 0개를 놓고 고민해보면 된다. 그래도 이해가 안되면 집에 있는 저금통을 탈탈 털어서 생각해 보자. -_-;; 언젠가 그림이 추가될 수도 있다.)
이제, 순열대칭군에 대해서 생각해 보자. 지금까지 말한건 뭐냐 하는 사람도 있겠지만, 연습문제였다.
(a, b)가 있다고 하자. 이걸 늘어놓는 방법의 수는 어떻게 될까? 당연히 2가지다. (a, b)와 (b, a)가 된다. 그럼, 이것을 이렇게 쓸 수 있다. ({a, a}, {b, b})와 ({a, b}, {b, a})라고 써보자. {x, y}는 x를 y로 바꾼다는 뜻이다. 여기서, "바꾼다"라는 동사가 들어갔음에 유의하자. 영어로는 이것을 Operation이라고 한다. 그런데, 사실 앞에 있는 a와 b는 어차피 순서대로 쓸 것이기 때문에, 이제부터는 그냥 (a, b)와 (b, a)라고 그냥 쓰자. 하지만, 여기서 엄청난 변화가 생기게 된다. 이제, "바꾼다"라는 것을 여러번 할 수 있게 된 것이다. 가령 (a, b)를 두번 적용할 수 있다. 물론 여기서 이것은 아무것도 바꾸지 않기 때문에 두번을 적용하든 세번을 적용하든 그냥 그대로 놔두는 것이 된다.
이제, 여기서부터, 순열을 군의 한 종류로 생각해볼 수 있다는 점을 알 수 있다.
군(Group)이란 다음과 같은 재미있는 성질을 가진 어떤 집합을 말한다.
1. 이항연산(Binary operation)이 잘 정의된다. 즉, 어떤 군 G가 있을 때, 이 군의 원소 a, b가 있다고 하고, 이항연산 ?가 있다고 하면, a?b가 다시 군 G의 원소이다. 이 말은, a, b를 알려주면 그걸 갖고 이항연산을 한 후에 어떤 원소가 되는지 알려주는 규칙을 잘 찾아낼 수 있다는 것이다.
2. 이항연산 ?가 있으면, 임의의 원소 a에 대해서 항등원이 있다. 즉, a?e = e?a = a인 원소 e가 있다.
3. 이항연산 ?가 있으면, 임의의 원소 a에 대해서 그 역원이 있다. 즉, 항등원 e에 대해서 a?b = b?a = e가 되는 원소 b가 항상 있다. 이때, b = -a라고 쓴다. (흔히들.)
이런 세가지 규칙을 만족하는 집합을 군이라고 부른다. 순열이 왜 군이 되는지 검토해 보자.
가령, (a, b)를 바꾸는 연산을 모아놓는다고 하면, (a, b)를 그대로 놔두는 것(e)이 하나 있고, (b, a)로 바꾸는 것(x)이 하나 있다. 여기에 대해서 이항연산이란, 이런 작용들을 연속으로 작용하는 것을 말한다. 가령, x?e라고 하면 e를 먼저 작용하고 x를 작용한다는 뜻이다. 이것은 잘 정의되는 이항연산인데, (a, b)에 대해서 바꿔주는 것들은 어떻게 바꿔주더라도 하나의 순열을 적용한 것으로 나타낼 수 있다. 원소의 수가 늘어나도 마찬가지이다. (a, b, c, d)를 (c, a, d, b)로 바꿔주는 작용과 (a, c, d, b)로 바꿔주는 작용을 연속적으로 작용시키면, 그 결과물 역시 한번에 바꿔주는 작용의 하나에 속한다. (직접 해보자. 절대, 귀찮아서 시키는거 아님.)
이런 늘어놓는 대칭성을, n개의 원소에 대해서 늘어놓는 것들에 대한 대칭성을 $S_n$이라고 부른다. 그럼, 여기서 $S_n$은 다시 우순열(Even permutation)과 기순열(Odd permutation)으로 나눌 수 있다. 한번에 2개씩만 바꾸는 행동을 여러 번 반복해서 모든 순열을 얻을 수 있는데, 그중 짝수번 반복해서 얻을 수 있는 것들은 우순열, 홀수번 반복해서 얻을 수 있는 것들은 기순열이 된다. 물론 이 두 집합은 $S_n$을 정확히 반으로 나눈다.
가령, (a, b, c, d)를 한번에 2개씩만 바꿔서 (d, b, a, c)를 만들려면, (a, b, c, d)->(a, b, d, c)->(d, b, a, c)가 된다. 3번 바꿔서 만들어야 하므로 (d, b, a, c)는 기순열이다.
사실, 우순열들만 다 모아두면 그것은 또한 다시 군을 이룬다. 이런것을 부분군이라고 하는데, 어떤 군의 부분집합이 다시 그 자체로 군이 되는 경우이다.
RECENT COMMENT